Submission #1156616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156616		spycoderyt	Vudu (COCI15_vudu)	C++20	42 / 140	233 ms	8244 KiB

vudu

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
const int off = N/2;
int fen[N];
void add(int pos,int val) {
    for(int i = pos;i<N;i+=i&-i)fen[i]+=val;
}
int sum(int pos){
    int res=0;
    for(int i = pos;i>0;i-=i&-i)res+=fen[i];
    return res;
}
int main() {
    int n,p,cur=0,ans=0;
    cin >> n;
    vector<int>v(n+1),pref(n+1);
    for(int i = 1;i<=n;i++)cin>>v[i];
    cin>>p;
    for(int i = 1;i<=n;i++)v[i] -= p;
    add(0+off,1);
    for(int i = 1;i<=n;i++) {
        pref[i] = pref[i-1] + v[i];
        cur += v[i];
        // cur - pref  >= 0 so pref <= cur
        ans+=sum(cur+off);
        add(pref[i]+off,1);
        // if(v[i]>=0)ans++;
        // cerr<<ans<<"\n";
    }
    cout << ans;
}

• Subtask 1: 42 / 140