Submission #1230661

#TimeUsernameProblemLanguageResultExecution timeMemory
1230661hitsuujVudu (COCI15_vudu)C++20
42 / 140
489 ms12448 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define pii pair<int,int> #define fi first #define se second #define inf LLONG_MAX #define ti tuple<int,int,int> const int lim=1e6; vector<int>tri(lim+10); int n,m; int seek(int x){ int cnt=0; while(x>=1){ cnt+=tri[x]; x-=x&-x; } return cnt; } void upd(int x){ while(x<=m){ tri[x]++; x+=x&-x; } } vector<int>c; int cm(int x){ int cek=lower_bound(c.begin(),c.end(),x)-c.begin()+1; return cek; } signed main(){ cin>>n;vector<int>a(n+1);for(int i=1;i<=n;i++) cin>>a[i]; int p;cin>>p; int pref=0; int ans=0; for(int i=1;i<=n;i++){ pref+=a[i]; a[i]=pref-p*i; c.pb(a[i]); } c.pb(0); sort(c.begin(),c.end()); c.erase(unique(c.begin(),c.end()),c.end()); m=c.size(); upd(cm(0)); for(int i=1;i<=n;i++){ // cout<<"cek "<<cm[a[i]]<<" "<<seek(cm[a[i]])<<endl; ans+=seek(cm(a[i])); upd(cm(a[i])); // cout<<i<<" "<<seek(cm[a[i]])<<endl; } cout<<ans; } // (pref[r]-pref[l-1])>= p(r-l+1) // pref[r]-pr>=pref[l-1]-pl+p
#Verdict Execution timeMemoryGrader output
Fetching results...