Submission #1230417

#TimeUsernameProblemLanguageResultExecution timeMemory
1230417warrennVudu (COCI15_vudu)C++20
42 / 140
654 ms94320 KiB
#include<bits/stdc++.h> using namespace std; int n,p; int a[1000002]; long long b[1000002]; long long pref[1000002]; map<long long,int>conv; int cnt=1; vector<long long>tmp; vector<int>bit; void update(int x,int val){ for(int q=x;q<=cnt;q+=(q&-q)){ bit[q]+=val; } } long long get(long long idx){ long long 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); long long 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...