比赛 2024暑假C班集训C 评测结果 AAAAAAAAAA
题目名称 灯笼 最终得分 100
用户昵称 liuyiche 运行时间 2.056 s
代码语言 C++ 内存使用 7.67 MiB
提交时间 2024-07-12 11:12:27
显示代码纯文本
#include <bits/stdc++.h>
            
using namespace std;

typedef long long ll;

ll ans = 0;
int n, m, x;
struct node
{
    vector<int> v;
};
node vis[100005];
int a[100005];
const int Add = 10000;
int tag[405];
vector<int> cnt1(100005);
vector<int> q(100005);
vector<int> qq(100005);
int L[405];
int R[405];
int blog[100005];

inline void build()
{
    int block = sqrt(n*log2(n));
    int num = n/block;
    if(n%block != 0)
        num++;
    qq = q;
    for(int i = 1; i <= num; ++i)
    {
        L[i] = (i-1)*block+1;
        R[i] = i*block; 
        R[i] = min(R[i],n);
        for(int j = L[i]; j <= R[i]; ++j)
            blog[j] = i;
        sort(q.begin()+L[i],q.begin()+R[i]+1,greater<int>());
    }
}

inline void solve(int l, int r)
{
    if(blog[l] == blog[r])
    {
        for(int i = l; i <= r; ++i)
        {
            if(qq[i]-qq[l-2] < x)
                continue;
            ans++;
        }
    }
    else
    {
        for(int i = l; i <= R[blog[l]]; ++i)
        {
            if(qq[i]-qq[l-2] < x)
                continue;
            ans++;
        }
        for(int i = L[blog[r]]; i <= r; ++i)
        {
            if(qq[i]-qq[l-2] < x)
                continue;
            ans++;
        }
        for(int i = blog[l]+1; i < blog[r]; ++i)
        {
            int p = upper_bound(q.begin()+L[i],q.begin()+R[i]+1,x+qq[l-2],greater<int>())-q.begin()-1;
            ans += p-L[i]+1;
        }
    }
}

inline void add(int l, int r)
{
    if(blog[l] == blog[r])
        for(int i = l; i <= r; ++i)
            cnt1[i]--;
    else
    {
        for(int i = l; i <= R[blog[l]]; ++i)
            cnt1[i]--;
        for(int i = L[blog[r]]; i <= r; ++i)
            cnt1[i]--;
        for(int i = blog[l]+1; i < blog[r]; ++i)
            tag[i]++;
    }
}

inline void Erase(int pos)
{
    vis[a[pos]+Add].v.erase(vis[a[pos]+Add].v.begin());
    int id;
    if(vis[a[pos]+Add].v.size() > 0)
        id = vis[a[pos]+Add].v.front();
    else
        id = n+1;
    add(pos+1,id-1);
}
    
int main()
{
    freopen("lantern.in", "r", stdin);
    freopen("lantern.out", "w", stdout);
        
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
            
    cin >> n >> m >> x;
    //cout << sqrt(n*log2(n)) << '\n';
    for(int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        q[i] = q[i-1]+a[i];
    }
    for(int i = 1; i <= n; ++i)
    {
        vis[a[i]+Add].v.push_back(i);
        cnt1[i] = cnt1[i-1];
        if(vis[a[i]+Add].v.size() == 1)
            cnt1[i]++;
    }
    build();
    //for(int i = 1; i <= n; ++i)
    //    cout << q[i] << " ";
    //cout << '\n';
    for(int i = 1; i < n; ++i)
    {
        int l = i+1, r = n;
        while(l != r)
        {
            int mid = (l+r+1)/2;
            if(cnt1[mid]-tag[blog[mid]] <= m)
                l = mid;
            else
                r = mid-1;
        }
        //cout << l << '\n'; 
        solve(i+1,l);
        //cout << ans << '\n';
        Erase(i);
    }
    
    ans *= 2;
    for(int i = 1; i <= n; ++i)
        if(a[i] >= x)
            ans++;
    cout << ans; 
    
   	return 0;
}