Submission #1160343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160343		Kalata_56	Vudu (COCI15_vudu)	C++20	42 / 140	1097 ms	17996 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;
int main(){
    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];
    for(long long i=1;i<N;i++){
        pre[i]=pre[i-1]+mas[i];
    }
    long long ans=0;
    a.insert(0);
    a.insert(maxa*N+1);
    for(long long i=0;i<N;i++){
        set<long long>::iterator b=a.upper_bound(pre[i]);

        //for(set<long long>::iterator j=a.begin();j!=a.end();j++){
           // cout<<*j<<" ";
        //}
        //cout<<endl;
        //cout<<*b<<endl;

        ans+=(distance(a.begin(),b));

        a.insert(pre[i]);

    }
    cout<<ans<<endl;
    return 0;

}

• Subtask 1: 42 / 140