Submission #948022

#TimeUsernameProblemLanguageResultExecution timeMemory
948022vjudge306Vudu (COCI15_vudu)C++14
140 / 140
670 ms43004 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> #define nn "\n" #define x_x ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define intt int _; cin >> _; while (_--) #define emp push_back #define mod 1000000007 #define all(v) v.begin(), v.end() #define ld long double #define A first #define B second //#define int long long typedef long long ll; const ld eps = 1e-27; // diff between decimals 0.000000001 mt19937 mt(time(nullptr)); ll sgt[4000003]; //int x[4000003]; void upd(int l, int r, int ind, int i) { if (r<ind||l>ind) return ; if(l!=r) { int mid=(l+r)/2; upd(l,mid,ind,i*2+1); upd(mid+1, r, ind, i*2+2); } if(l==r&&l==ind) {sgt[i]++; return ;} sgt[i]=sgt[i*2+1]+sgt[i*2+2]; } ll sum(int l, int r, int s, int e, int i) { if(r<s||l>e) return 0; if(l>=s&&r<=e)return sgt[i]; int mid=(l+r)/2; return sum(l,mid,s,e,i*2+1)+sum(mid+1, r, s, e, i*2+2); } int main() { x_x int n; cin>>n; ll p, sm=0, ar[n]; for(auto&i:ar)cin>>i; cin>>p; ll ans=0; vector<ll>tr,v; for(ll i=1; i<=n; i++) { sm+=ar[i-1]; ll x=-p*i; x+=sm; tr.emp(x); } tr.emp(0); sort(all(tr)); v.emp(tr[0]); for(auto i:tr) { if(i!=v.back()) v.emp(i); } sm=0; int ind=lower_bound(all(v),0)-v.begin(); upd(0,v.size(), ind,0); for (ll i=1; i<=n; i++) { sm+=ar[i-1]; ll x=p*i; x=sm-x; int j=upper_bound(all(v), x)-v.begin(); --j; if (j>=0) { ans+=sum(0, v.size(), 0, j, 0); } x=-p*i; x+=sm; j=lower_bound(all(v),x)-v.begin(); upd(0,v.size(),j,0); } cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...