Submission #60051

#TimeUsernameProblemLanguageResultExecution timeMemory
60051Adhyyan1252Vudu (COCI15_vudu)C++11
56 / 140
1094 ms66560 KiB
#include<bits/stdc++.h> // 6 47 typedef long long ll; #define NMAX 1000005 #define SMAX 2300000 using namespace std; int tree[SMAX]; void upd(int i, int s, int e, int indx){ if(s == e){ tree[i] = 1; return; } int m = (s + e)>>1; if(indx <= m) upd(i*2, s, m, indx); else upd(i*2+1, m+1, e, indx); tree[i] = tree[i*2] + tree[i*2+1]; } ll query(int i, int s, int e, int l, int r){ if(s >= l && e <= r) return tree[i]; else if(s > r || e < l) return 0; int m = (s + e)>>1; return query(i*2, s, m, l, r) + query(i*2+1, m+1, e, l, r); } int main(){ int n; cin>>n; ll a[n]; for(int i = 0; i < n; i++){ cin>>a[i]; } ll p; cin>>p; vector<pair<ll, int> > vi; ll zero = 0; for(int i = n-1; i >= 0; i--){ a[i] -= p; zero -= a[i]; ll cur = zero + a[i]; //cout<<i<<" PUSH: "<<cur<<endl; vi.push_back({cur, i}); } sort(vi.begin(), vi.end()); vector<int> indx(n); for(int i = 0; i < n; i++){ indx[vi[i].second] = i; } ll ans = 0; zero = 0; for(int i = n-1; i >= 0; i--){ upd(1, 0, n-1, indx[i]); zero -= a[i]; pair<ll, int> temp = {zero, 0}; int index = lower_bound(vi.begin(), vi.end(), temp ) - vi.begin(); ans += query(1, 0, n-1, index, n-1); } cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...