Submission #731321

#TimeUsernameProblemLanguageResultExecution timeMemory
731321bgnbvnbvVudu (COCI15_vudu)C++14
140 / 140
390 ms33580 KiB
#include<bits/stdc++.h> #define TASKNAME "codeforce" #define pb push_back #define pli pair<int,int> #define fi first #define se second #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); using namespace std; using ll=long long; const ll maxN=2e6; const ll inf=1e18; const ll mod=1e9+7; vector<ll>vec; ll bit[maxN]; ll n; void update(ll p) { p=lower_bound(vec.begin(),vec.end(),p)-vec.begin()+1; while(p<=n) { bit[p]++; p+=(p&(-p)); } } ll get(ll p) { ll res=0; while(p>0) { res+=bit[p]; p-=(p&(-p)); } return res; } ll a[maxN],p; void solve() { cin >> n; ll ans=0; for(int i=1;i<=n;i++) cin >> a[i]; cin >> p; for(int i=1;i<=n;i++) a[i]-=p,a[i]+=a[i-1],vec.pb(a[i]); sort(vec.begin(),vec.end()); update(0); for(int i=1;i<=n;i++) { ll p=upper_bound(vec.begin(),vec.end(),a[i])-vec.begin(); ans+=get(p); update(a[i]); } cout << ans; } int main() { fastio //freopen(TASKNAME".INP","r",stdin); //freopen(TASKNAME".OUT","w",stdout); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...