제출 #1160354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160354		Kalata_56	Vudu (COCI15_vudu)	C++20	84 / 140	385 ms	48096 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];


long long tree[4000001];
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-1,0,dve[i].second);
        update(1,0,N-1,dve[i].second);
        otg+=kolko;
    }
    cout<<otg<<endl;
    return 0;

}

• Subtask 1: 84 / 140