Submission #762749

#TimeUsernameProblemLanguageResultExecution timeMemory
762749ETheBest3Vudu (COCI15_vudu)C++14
42 / 140
1016 ms58464 KiB
#include<bits/stdc++.h> #define endl "\n" #define lli int using namespace std; const lli MAXN=1000005; lli N, a[MAXN], P, pref[MAXN], tree[MAXN], ss[MAXN], ans; unordered_map<lli, lli> m; void update(lli i, lli d){ while(i<=N+1){ tree[i]+=d; i+=i&(-i); } return; } lli query(lli i){ lli otg=0; while(i>0){ otg+=tree[i]; i-=i&(-i); } return otg; } int main() { ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); cin>>N; for(lli i=1; i<=N; i++){ cin>>a[i]; } cin>>P; for(lli i=1; i<=N; i++){ a[i]-=P; pref[i]=pref[i-1]+a[i]; ss[i]=pref[i]; } sort(ss, ss+N+1); lli k=1; for(lli i=0; i<=N; i++){ if(i!=0 and ss[i]==ss[i-1])continue; m[ss[i]]=k; k++; } update(m[0], 1); for(lli i=1; i<=N; i++){ ans+=query(m[pref[i]]); update(m[pref[i]], 1); } cout<<ans<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...