Submission #1356577

#TimeUsernameProblemLanguageResultExecution timeMemory
1356577njoopVudu (COCI15_vudu)C++20
140 / 140
146 ms32588 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct fwt {
    int n;
    vector<int> bit;

    void init(int sz) {
        n=sz;
        bit.assign(n+2, 0);
    }

    void update(int idx, int val) {
        for(; idx <= n; idx = idx|(idx+1)) {
            bit[idx] += val;
        }
    }

    int pref(int idx) {
        int res=0;
        for(; idx >= 0; idx = (idx&(idx+1))-1) {
            res += bit[idx];
        }
        return res;
    }

    int query(int l, int r) {
        if(l > r) return 0;
        if(l == 0) return pref(r);
        return pref(r)-pref(l-1);
    }
};

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, p, ans=0;
    cin >> n;
    fwt fw;
    fw.init(n);
    vector<int> arr(n+2, 0);
    vector<pair<int, int>> val;
    for(int i=1; i<=n; i++) {
        cin >> arr[i];
    }
    cin >> p;
    for(int i=1; i<=n; i++) {
        arr[i] += arr[i-1]-p;
        if(arr[i] >= 0) ans++;
        val.push_back({arr[i], i});
    }
    sort(val.begin(), val.end());
    for(auto i: val) {
        ans += fw.query(0, i.second);
        fw.update(i.second, 1);
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...