제출 #456369

#제출 시각아이디문제언어결과실행 시간메모리
456369Sarah_MokhtarVudu (COCI15_vudu)C++14
42 / 140
1098 ms65540 KiB
#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,idx; int tree[N<<2],sum; 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'; }
#Verdict Execution timeMemoryGrader output
Fetching results...