oj.uz

Submission #219220

# Submission time Handle Problem Language Result Execution time Memory
219220 2020-04-04T15:57:26 Z DavidDamian Vudu (COCI15_vudu) C++11
140 / 140
 395 ms 23928 KB 
#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;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 640 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 395 ms 23160 KB Output is correct
5 Correct 205 ms 13560 KB Output is correct
6 Correct 339 ms 20732 KB Output is correct
7 Correct 334 ms 21368 KB Output is correct
8 Correct 305 ms 18936 KB Output is correct
9 Correct 378 ms 23928 KB Output is correct
10 Correct 331 ms 20984 KB Output is correct