比赛 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;
}