Submission #94408

#	Time	Username	Problem	Language	Result	Execution time	Memory
94408		theknife2001	Vudu (COCI15_vudu)	C++17	42 / 140	1077 ms	66560 KiB

vudu

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N=1e6+55;
ll a[N];
ll sum[N];
multiset < ll > st;

int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int P;
    cin>>P;
    for(int i=0;i<n;i++)
    {
        sum[i]=a[i]-P;
        if(i)
            sum[i]+=sum[i-1];
        st.insert(sum[i]);
    }
    ll ans=0;
    ll x=0;
    for(int i=0;i<n;i++)
    {
        ans+=distance(st.lower_bound(x),st.end());
        st.erase(st.find(sum[i]));
        x+=a[i]-P;
    }
    cout<<ans<<endl;
    return 0;
}

• Subtask 1: 42 / 140