Submission #1160356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160356		Kalata_56	Vudu (COCI15_vudu)	C++20	140 / 140	384 ms	48048 KiB

vudu

#include<bits/stdc++.h>
using namespace std;
long long mas[1000011];
long long pre[1000011];
pair<long long,long long> dve[1000011];
long long tree[4000011];
void update(long long in,long long l,long long r,long long koj){
    if(l==r){
        tree[in]++;
        return ;
    }
    long long 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 ;
}
long long ans(long long in,long long l,long long r,long long ot,long long du){
    if(l>=ot && r<=du){
        return tree[in];
    }
    long long mid=(l+r)/2;
    long long 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));
    long long otg=0;
    for(long long i=0;i<=N;i++){

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

}

• Subtask 1: 140 / 140