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