Submission #219214

#	Time	Username	Problem	Language	Result	Execution time	Memory
219214		DavidDamian	Vudu (COCI15_vudu)	C++11	98 / 140	827 ms	65540 KiB

vudu

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
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;
}
typedef pair<ll,int> pii;
map<ll,int> remap;
ll k;
ll A[1000006]; //S[i]-k*i
//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;
    remap[0]=1;
    for(ll i=1;i<=n;i++){
        A[i]=A[i]-k*i; //S_K[i]=A[i]-k*i
        remap[ A[i] ]=1;
    }
    int id=1;
    for(pii p: remap){
        remap[p.first]=id++;
    }
    for(int i=0;i<=n;i++){
        A[i]=remap[ A[i] ];
    }
    remap.clear();
    ll total=0;
    for(int i=0;i<=n;i++){
        if(i>0) total+=(ll)getSum(1,A[i]);
        update(A[i],1);
    }
    cout<<total<<'\n';
    return 0;
}

• Subtask 1: 98 / 140