#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define read freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#define LESSGO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const ll N=1e6+10,M=505,OO=1e16,mod=1e9+7;
ll n,k,a[N],ans,sum;
int tree[N<<2],idx;
vector<ll>prefixes;
map<ll,int>val;
void compress(){
sort(prefixes.begin(),prefixes.end());
ll prev=-1;
for(ll i:prefixes){
if(i!=prev) ++idx;
val[i]=idx;
prev=i;
}
}
void update(int node,int st,int en,int idx,int val){
if(st==en){
tree[node]+=val;
return;
}
int mid=(st+en)>>1;
if(idx<=mid) update(2*node,st,mid,idx,val);
else update(2*node+1,mid+1,en,idx,val);
tree[node]=tree[2*node]+tree[2*node+1];
}
int get(int node,int st,int en,int l,int r){
if(en<l||st>r) return 0;
if(st>=l&&en<=r) return tree[node];
int mid=(st+en)>>1;
return get(2*node,st,mid,l,r)+get(2*node+1,mid+1,en,l,r);
}
int main(){
LESSGO;
cin>>n;
for(int i=0;i<n;++i){
cin>>a[i];
}
cin>>k;
for(int i=0;i<n;++i){
a[i]-=k;
sum+=a[i];
prefixes.push_back(sum);
}
prefixes.push_back(0);
compress();
sum=0;
for(int i=0;i<n;++i){
sum+=a[i];
ans+=get(1,0,n-1,0,val[sum]);
update(1,0,n-1,val[sum],1);
if(sum>=0) ++ans;
}
cout<<ans<<'\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
844 KB |
Output is correct |
2 |
Correct |
5 ms |
816 KB |
Output is correct |
3 |
Correct |
6 ms |
716 KB |
Output is correct |
4 |
Runtime error |
477 ms |
65540 KB |
Execution killed with signal 9 |
5 |
Correct |
792 ms |
51236 KB |
Output is correct |
6 |
Runtime error |
462 ms |
65540 KB |
Execution killed with signal 9 |
7 |
Runtime error |
466 ms |
65540 KB |
Execution killed with signal 9 |
8 |
Runtime error |
537 ms |
65540 KB |
Execution killed with signal 9 |
9 |
Runtime error |
476 ms |
65540 KB |
Execution killed with signal 9 |
10 |
Runtime error |
434 ms |
65540 KB |
Execution killed with signal 9 |