#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int bit[1000006];
int n;
void update(int i,int v)
{
while(i<=n+5){
bit[i]+=v;
i+=(i&(-i));
}
}
int query(int i)
{
int ans=0;
while(i>0){
ans+=bit[i];
i-=(i&(-i));
}
return ans;
}
ll getSum(int a,int b)
{
ll ans=(ll)query(b)-(ll)query(a-1);
return ans;
}
int remap[1000006];
ll k;
ll A[1000006]; //S[i]-k*i
ll ordered[1000006];
int binarySearch(ll x)
{
int pos=-1;
for(int b=n+5;b>=1;b/=2){
while(pos+b<=n && ordered[pos+b]<=x) pos+=b;
}
return pos;
}
//ll S_K[1000006];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>A[i];
A[i]+=A[i-1];
}
cin>>k;
for(ll i=1;i<=n;i++){
A[i]=A[i]-k*i; //S_K[i]=A[i]-k*i
ordered[i]=A[i];
}
sort(ordered,ordered+n+1);
int id=0;
for(int i=0;i<=n;i++){
remap[i]=++id;
while(i<n && ordered[i]==ordered[i+1]){
i++;
remap[i]=id;
}
}
for(int i=0;i<=n;i++){
int pos=binarySearch(A[i]);
A[i]=remap[pos];
}
ll total=0;
update(A[0],1);
for(int i=1;i<=n;i++){
total+=(ll)getSum(1,A[i]);
update(A[i],1);
}
cout<<total<<'\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
640 KB |
Output is correct |
2 |
Correct |
6 ms |
512 KB |
Output is correct |
3 |
Correct |
6 ms |
512 KB |
Output is correct |
4 |
Correct |
407 ms |
32376 KB |
Output is correct |
5 |
Correct |
215 ms |
18040 KB |
Output is correct |
6 |
Correct |
331 ms |
28792 KB |
Output is correct |
7 |
Correct |
334 ms |
29816 KB |
Output is correct |
8 |
Correct |
306 ms |
23288 KB |
Output is correct |
9 |
Correct |
404 ms |
33400 KB |
Output is correct |
10 |
Correct |
354 ms |
29176 KB |
Output is correct |