Submission #950265

#TimeUsernameProblemLanguageResultExecution timeMemory
950265vjudge1Vudu (COCI15_vudu)C++17
140 / 140
840 ms50112 KiB
#include <bits/stdc++.h> #define ll long long #define ff first #define ss second #define pb push_back #define all(x) x.begin(),x.end() using namespace std; const int N=1e6+5; ll t[N*4],a[N]; vector <ll> v; ll get(int v,int tl,int tr,int l,int r){ if(r<tl or tr<l)return 0; if(l<=tl && tr<=r)return t[v]; int tm=(tl+tr)/2; return get(v*2,tl,tm,l,r)+get(v*2+1,tm+1,tr,l,r); } void update(int v,int tl,int tr,int pos){ if(tl==tr)t[v]++; else{ int tm=(tl+tr)/2; if(pos<=tm)update(v*2,tl,tm,pos); else update(v*2+1,tm+1,tr,pos); t[v]=t[v*2]+t[v*2+1]; } } signed main(){ ios_base::sync_with_stdio(); cin.tie(0);cout.tie(0); int n,p; cin>>n; for(int i=0;i<n;i++)cin>>a[i]; cin>>p; ll sum=0,x=0,y=0; for(int i=0;i<n;i++){ x=i;y=p; x*=y; v.pb(sum-x); x=a[i]; sum+=x; x=i;y=p; x*=y; v.pb(sum-x-p); } sort(all(v)); v.erase(unique(v.begin(),v.end()),v.end()); sum=0; ll ans=0; for(int i=0;i<n;i++){ x=i;y=p; x*=y; auto pos=lower_bound(all(v),sum-x)-v.begin(); update(1,1,v.size(),pos+1); x=a[i]; sum+=x; x=i;y=p; x*=y; pos=lower_bound(all(v),sum-x-p)-v.begin(); ans+=get(1,1,v.size(),1,pos+1); } cout<<ans<<"\n"; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...