Submission #1230656

#TimeUsernameProblemLanguageResultExecution timeMemory
1230656hitsuujVudu (COCI15_vudu)C++20
42 / 140
1099 ms131072 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #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); map<int,int>cm; 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<=n){ tri[x]++; x+=x&-x; } } 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; set<int>c; for(int i=1;i<=n;i++){ pref+=a[i]; a[i]=pref-p*i; c.insert(a[i]); } c.insert(0); vector<int>sorted; for(auto x:c) sorted.pb(x); for(int i=0;i<sorted.size();i++){ cm[sorted[i]]=i+1; } m=sorted.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...