Submission #1230207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230207		KindaNameless	Vudu (COCI15_vudu)	C++20	140 / 140	222 ms	20396 KiB

vudu

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double

struct BIT {
    vector<int> fen;
    int N;

    BIT(int _N) : N(_N + 5) {
        fen = vector<int>(N + 5, 0);
    }

    void upd(int x, int v) {
        while(x <= N) {
            fen[x] += v;
            x += x & -x;
        }
    }

    int prefix(int x) {
        int res = 0;
        while(x > 0) {
            res += fen[x];
            x -= x & -x;
        }
        return res;
    }
};

BIT bit(1000000);

void solve() {
    int N; cin >> N;

    vector<ll> Pref(N + 1);
    for(int i = 1; i <= N; ++i) {
        ll A; cin >> A;
        Pref[i] = A + Pref[i - 1];
    }

    ll P; cin >> P;

    vector<ll> comp;
    for(int i = 0; i <= N; ++i) {
        comp.push_back(Pref[i] - P * (ll)i);
    }

    sort(comp.begin(), comp.end());

    ll answer = 0;
    for(int i = 0; i <= N; ++i) {
        int pos = lower_bound(comp.begin(), comp.end(), Pref[i] - P * (ll)i) - comp.begin() + 1;
        answer += (ll)bit.prefix(pos);
        bit.upd(pos, 1);
    }

    cout << answer;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int tc = 1; //cin >> tc;

    while(tc--) {
        solve();
    }

    return 0;
}

• Subtask 1: 140 / 140