比赛 |
2024暑假C班集训C |
评测结果 |
AAAAAAAAAA |
题目名称 |
灯笼 |
最终得分 |
100 |
用户昵称 |
darkMoon |
运行时间 |
0.998 s |
代码语言 |
C++ |
内存使用 |
14.61 MiB |
提交时间 |
2024-07-12 10:32:25 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
// #define fin cin
// #define fout cout
ifstream fin("lantern.in");
ofstream fout("lantern.out");
auto mread = [](){
int x;
fin >> x;
return x;
};
const int N = 1e5 + 5;
int n = mread(), m = mread(), k = mread(), a[N], s[N], l[N], belong[N], s2[N];
set<pair<int, int> > se;
map<int, int> ap;
void add(int x, int k){
while(x <= n + 1){
s2[x] += k;
x += x & -x;
}
return;
}
int query(int x){
int ans = 0;
while(x){
ans += s2[x];
x -= x & -x;
}
return ans;
}
void build(){
int l = 1, sum[20005] = {0}, now = 0;
::l[1] = 1;
now = 1, sum[a[1] + 10000] = 1;
for(int i = 2; i <= n; i ++){
sum[a[i] + 10000] ++;
if(sum[a[i] + 10000] == 1){
now ++;
}
while(now > m){
sum[a[l] + 10000] --;
if(sum[a[l] + 10000] == 0){
now --;
}
l ++;
}
::l[i] = l;
}
return;
}
signed main(){
for(int i = 1; i <= n; i ++){
a[i] = mread();
s[i] = a[i] + s[i - 1];
ap[s[i]] = 0;
}
build();
ap[0] = 0;
{
int now = 0;
for(auto &t : ap){
t.se = ++now;
se.insert(t);
// printf("--- %lld %lld\n", t.fi, t.se);
}
}
for(int i = 1; i <= n; i ++){
belong[i] = ap[s[i]];
}
int ans = 0;
belong[0] = ap[0];
add(belong[0], 1);
add(belong[1], 1);
if(a[1] >= k){
ans ++;
}
int nl = 1;
for(int i = 2; i <= n; i ++){
while(nl < l[i]){
add(belong[nl - 1], -1);
nl ++;
}
auto it = se.upper_bound(mp(s[i] - k, LONG_LONG_MAX));
if(it != se.begin()){
it --;
int tmp = (*it).se;
ans += query(tmp);
// printf("*** %lld %lld %lld %lld %lld\n", i, l[i], belong[i], s[i] - k, tmp);
}
add(belong[i], 1);
}
ans += ans;
for(int i = 1; i <= n; i ++){
if(a[i] >= k)
ans -= 1;
}
fout << ans;
return 0;
}