Submission #219211

#TimeUsernameProblemLanguageResultExecution timeMemory
219211DavidDamianVudu (COCI15_vudu)C++11
56 / 140
510 ms65540 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; ll bit[1000006]; int n; void update(int i,int v) { while(i<=n){ bit[i]+=v; i+=(i&(-i)); } } int query(int i) { int ans=0; while(i>0){ ans+=bit[i]; i-=(i&(-i)); } return ans; } int getSum(int a,int b) { return query(b)-query(a-1); } typedef pair<ll,int> pii; map<ll,int> remap; ll k; ll A[1000006]; ll S[1000006]; ll S_K[1000006]; //S[i]-k*i int main() { ios_base::sync_with_stdio(0);cin.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>A[i]; } cin>>k; remap[0]=1; for(ll i=1;i<=n;i++){ S[i]=S[i-1]+A[i]; S_K[i]=S[i]-k*i; remap[ S_K[i] ]=1; } int id=1; for(pii p: remap){ remap[p.first]=id++; } ll total=0; for(int i=0;i<=n;i++){ S_K[i]=remap[ S_K[i] ]; if(i>0) total+=getSum(1,S_K[i]); update(S_K[i],1); } cout<<total<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...