Submission #219220

#TimeUsernameProblemLanguageResultExecution timeMemory
219220DavidDamianVudu (COCI15_vudu)C++11
140 / 140
395 ms23928 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; ///BIT ///Remap ///Binary Search ///Determine the number of contiguous subsequences with mean >= K ///A pair (i,j) is valid if and only if S[i]-S[j]>=(K)*(i-j) and j<i where S[i] is the sum from 1 to i ///We get S[i]-K*i >= S[j]-K*j for all j<i ///So for each i we count the id's j that are valid with the BIT (sum from 1 to A[i]) int bit[1000006]; int n; void update(int i,int v) { while(i<=n+5){ bit[i]+=v; i+=(i&(-i)); } } int query(int i) { int ans=0; while(i>0){ ans+=bit[i]; i-=(i&(-i)); } return ans; } ll getSum(int a,int b) { ll ans=(ll)query(b)-(ll)query(a-1); return ans; } int remap[1000006]; ll k; ll A[1000006]; //S[i]-k*i ll ordered[1000006]; int binarySearch(ll x) ///Finds the position of an integer x { int pos=-1; for(int b=n+5;b>=1;b/=2){ while(pos+b<=n && ordered[pos+b]<=x) pos+=b; } return pos; } //ll S_K[1000006]; int main() { ios_base::sync_with_stdio(0);cin.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>A[i]; A[i]+=A[i-1]; } cin>>k; for(ll i=1;i<=n;i++){ A[i]=A[i]-k*i; //S_K[i]=A[i]-k*i ordered[i]=A[i]; } sort(ordered,ordered+n+1); int id=0; for(int i=0;i<=n;i++){ remap[i]=++id; while(i<n && ordered[i]==ordered[i+1]){ i++; remap[i]=id; } } for(int i=0;i<=n;i++){ //Remaps the input int pos=binarySearch(A[i]); A[i]=remap[pos]; } ll total=0; update(A[0],1); for(int i=1;i<=n;i++){ total+=(ll)getSum(1,A[i]); update(A[i],1); } cout<<total<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...