Submission #1230407

#TimeUsernameProblemLanguageResultExecution timeMemory
1230407warrennVudu (COCI15_vudu)C++20
42 / 140
1098 ms66840 KiB
#include<bits/stdc++.h> using namespace std; int n,p; int a[1000002]; int b[1000002]; int pref[1000002]; map<int,int>conv; int cnt=1; vector<int>tmp,st; vector<int>bit; void update(int x,int val){ for(int q=x;q<=cnt;q+=(q&-q)){ bit[q]+=val; } } int get(int idx){ int res=0; for(int u=idx;u>0;u-=(u&-u)){ res+=bit[u]; } return res; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n; for(int q=1;q<=n;q++){ cin>>a[q]; } cin>>p; for(int q=1;q<=n;q++){ pref[q]=pref[q-1]+a[q]; b[q]=pref[q]-p*q; tmp.push_back(b[q]); } tmp.push_back(0); sort(tmp.begin(),tmp.end()); for(int q=0;q<tmp.size();q++){ if(q==0 || tmp[q-1]!=tmp[q]){ conv[tmp[q]]=cnt; cnt++; } } bit=vector<int>(cnt+3); int ans=0; update(conv[0],1); for(int q=1;q<=n;q++){ ans+=get(conv[b[q]]); // cout<<ans<<" "<<conv[b[q]]<<endl; update(conv[b[q]],1); } cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...