Submission #720675

#	Time	Username	Problem	Language	Result	Execution time	Memory
720675		Yell0	Vudu (COCI15_vudu)	C++17	140 / 140	303 ms	33556 KiB

vudu

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MN=1e6+2;
int N,P;
ll pfs[MN],cc[MN],bit[MN],ans=0;

ll qry(int idx) {
    ll out=0;
    for(int i=idx;i>0;i-=i&-i) out+=bit[i];
    return out;
}

void inc(int idx) {
    for(int i=idx;i<=MN;i+=i&-i) bit[i]++;
}

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>N;
    for(int i=1;i<=N;i++) cin>>pfs[i];
    cin>>P;
    for(int i=1;i<=N;i++) {
        pfs[i]+=pfs[i-1]-P;
        cc[i]=pfs[i];
    }
    sort(cc,cc+1+N);
    for(int i=0;i<=N;i++) {
        int r=lower_bound(cc,cc+1+N,pfs[i])-cc+1;
        ans+=qry(r);
        inc(r);
    }
    cout<<ans<<'\n';
    return 0;
}

• Subtask 1: 140 / 140