Submission #252723

#	Time	Username	Problem	Language	Result	Execution time	Memory
252723		NONAME	Vudu (COCI15_vudu)	C++14	140 / 140	394 ms	31792 KiB

vudu

#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;

const int N = int(1e6) + 10;

int n;
ll a[N], pf[N], p, fen[N];
vector <ll> vec;

ll sum(int x) { ll res = 0; while (x >= 0) res += fen[x], x = (x & (x + 1)) - 1; return res; }
void upd(int x) { while (x < int(vec.size())) ++fen[x], x = (x | (x + 1)); }

int main() {
    fast_io;

    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    cin >> p;

    for (int i = 0; i < n; ++i)
        pf[i] = (i - 1 < 0 ? 0 : pf[i - 1]) + a[i];

    vec.push_back(0);
    for (int i = 0; i < n; ++i) {
        ll vl = pf[i] - p * (i + 1);

        vec.push_back(vl);
    }

    sort(vec.begin(), vec.end());
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());

    //for (int i = 0; i < int(vec.size()); ++i)
        //cerr << vec[i] << " ";
    //cerr << "\n";

    upd(lower_bound(vec.begin(), vec.end(), 0ll) - vec.begin());
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        int ps = lower_bound(vec.begin(), vec.end(), pf[i] - p * (i + 1)) - vec.begin();
        //cerr << ps << "\n";

        ans += sum(ps);
        upd(ps);
    }

    cout << ans << "\n";
}

• Subtask 1: 140 / 140