Submission #950243

#TimeUsernameProblemLanguageResultExecution timeMemory
950243vjudge1Vudu (COCI15_vudu)C++17
56 / 140
625 ms65536 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]; 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; vector <int> a(n); for(int i=0;i<n;i++)cin>>a[i]; cin>>p; ll sum=0,x=0,y=0; vector <ll> v; 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)); int id=1; map <ll,int> ind; ind[v[0]]=id; for(int i=1;i<v.size();i++){ if(v[i]!=v[i-1]){ id++; ind[v[i]]=id; } } sum=0; ll ans=0; for(int i=0;i<n;i++){ x=i;y=p; x*=y; update(1,1,id,ind[sum-x]); x=a[i]; sum+=x; x=i;y=p; x*=y; ans+=get(1,1,id,1,ind[sum-x-p]); } cout<<ans<<"\n"; } /* */

Compilation message (stderr)

vudu.cpp: In function 'int main()':
vudu.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=1;i<v.size();i++){
      |                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...