Submission #1160352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160352		Kalata_56	Vudu (COCI15_vudu)	C++20	28 / 140	378 ms	39856 KiB

vudu

#include<bits/stdc++.h>
using namespace std;
long long N,M;
long long mas[1000001];
long long pre[1000001];
//multiset<long long> a;
pair<long long,long long> dve[1000001];


int tree[4000001];
void update(int in,int l,int r,int koj){
    if(l==r){
        tree[in]++;
        return ;
    }
    int mid=(l+r)/2;
    if(koj<=mid){
        update(in*2,l,mid,koj);
    }else{
        update(in*2+1,mid+1,r,koj);
    }
    tree[in]=tree[in*2]+tree[in*2+1];
    return ;
}
int ans(int in,int l,int r,int ot,int du){
    if(l>=ot && r<=du){
        return tree[in];
    }
    int mid=(l+r)/2;
    int quer=0;
    if(ot<=mid){
        quer+=ans(in*2,l,mid,ot,du);
    }if(du>mid){
        quer+=ans(in*2+1,mid+1,r,ot,du);
    }
    return quer;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    long long N,P;
    cin>>N;
    long long maxa=0;
    for(long long i=0;i<N;i++){
        cin>>mas[i];
        maxa=max(mas[i],maxa);
    }
    cin>>P;
    for(long long i=0;i<N;i++){
        mas[i]-=P;
    }
    pre[0]=mas[0];

    dve[0].first=0;
    dve[0].second=0;
    dve[1].first=mas[0];
    dve[1].second=1;
    for(long long i=1;i<N;i++){
        pre[i]=pre[i-1]+mas[i];
        dve[i+1].first=pre[i];
        dve[i+1].second=i+1;
    }
    sort(dve,dve+(N+1));
    int otg=0;
    for(int i=0;i<=N;i++){

        int kolko=ans(1,0,N-1,0,dve[i].second);
        update(1,0,N-1,dve[i].second);
        otg+=kolko;
    }
    cout<<otg<<endl;
    return 0;

}

• Subtask 1: 28 / 140