Submission #1230452

#TimeUsernameProblemLanguageResultExecution timeMemory
1230452warrennVudu (COCI15_vudu)C++20
140 / 140
235 ms39700 KiB
#include<bits/stdc++.h> using namespace std; #define int long long const int maxn=1e6+2; int n,p; int a[maxn]; int b[maxn]; int pref[maxn]; int cnt=1; vector<int>tmp; vector<int>bit; void update(int x,int val){ for(int q=x;q<=n+2;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 conv(int hah){ int idx=lower_bound(tmp.begin(),tmp.end(),hah)-tmp.begin(); return idx+1; } signed 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()); tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end()); bit=vector<int>(n+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...