Submission #1230447

#TimeUsernameProblemLanguageResultExecution timeMemory
1230447lioowVudu (COCI15_vudu)C++20
140 / 140
235 ms31752 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define pb push_back #define int long long #define repp(i,x,n) for(int i=x;i<=n;i++) #define rep(i,x,n) for(int i=x;i>=n;i--) #define cy cout<<"YES"<<endl #define cn cout<<"NO"<<endl #define ca cout<<"Alice"<<endl #define r0 return 0 #define fi first #define se second #define liow ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define jelek cout<<"jelek"<<endl #define pii pair<int,int> #define all(v) v.begin(),v.end() #define pi pair<pair<int,int>,pair<int,int>> #define p3 pair<int,pair<int,int>> #define p2 #define tp tuple<int,int,int> #define fl fflush(stdout) #define lb long double #define p5 pair<int,pair<pair<int,int>,pair<int,int>>> #pragma GCC optimize ("O2") #pragma GCC optimize ("unroll-loops") using namespace std; using namespace __gnu_pbds; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; const int mod=1e9+7; const int SQMAX=635,INF=1e18; //const int mod=998244353; //const int MOD=1e6+3; mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count()); pii dr[8]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}}; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; int dxx[4]={1,1,-1,-1}; int dyy[4]={1,-1,-1,1}; int mul(int x,int y){return (x%mod*y%mod)%mod;} int expo(int b,int e){ if(e==0) return 1; int tmp=expo(b,e/2); if(e%2) return mul(tmp,mul(tmp,b)); else return mul(tmp,tmp); } const int maxn=1e6+5; const int N=1e6; int BIT[maxn]; int n; int qry(int id){ int sum = 0; for(;id>=1;id-=id&-id) sum += BIT[id]; return sum; } void upd(int id, int v) { for(;id<=1e6;id+=id&-id) BIT[id]+=v; } int query(int l, int r){ return qry(r)- qry(l-1); } void upd_range(int l, int r, int v) { upd(l,v); upd(r+1,-v); } void solve(){ cin>>n; int a[n+2]; int pref[n+2]; pref[0]=0; vector<int>v; repp(i,1,n){ cin>>a[i]; pref[i]=pref[i-1]+a[i]; } int p;cin>>p; repp(i,1,n){ pref[i]-=i*p; v.pb(pref[i]); } sort(all(v)); v.erase(unique(all(v)),v.end()); upd(lower_bound(all(v),0)-v.begin()+1,1); int ans=0; repp(i,1,n){ int x=lower_bound(all(v),pref[i])-v.begin()+1; ans+=qry(x); // cout<<qry(x)<<endl; upd(x,1); } cout<<ans<<endl; } signed main(){ liow; int tc=1; // cin>>tc; while(tc--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...