Submission #1298712

#TimeUsernameProblemLanguageResultExecution timeMemory
1298712tabVudu (COCI15_vudu)C++20
140 / 140
465 ms64620 KiB
#include "bits/stdc++.h"
using namespace std;
#define intt long long
#define fi first
#define se second

const intt mxN = 1e5 + 5;
const intt LG = 20;
const intt inf = 1e18;  
const intt mod = 10007;

intt n, p;
vector<intt> a(mxN), pre(mxN), seg;

void update(intt node, intt l, intt r, intt pos) {
    if(l == r) {
        seg[node] = 1;
        return;
    }
    intt mid = (l + r) / 2;
    if(pos <= mid) update(node * 2, l, mid, pos);
    else update(node * 2 + 1, mid + 1, r, pos);
    seg[node] = seg[node * 2] + seg[node * 2 + 1];
}

intt get(intt node, intt l, intt r, intt ql, intt qr) {
    if(ql > r || qr < l || ql > qr) return 0ll;
    if(ql <= l && r <= qr) return seg[node];
    intt mid = (l + r) / 2;
    return get(node * 2, l, mid, ql, qr) + get(node * 2 + 1, mid + 1, r, ql, qr);
}

void _() {
    cin >> n;
    a.resize(n);
    pre.resize(n);
    seg.assign(4 * n + 1, 0ll);
    for(intt i = 0; i < n; i++) {
        cin >> a[i];
        pre[i] = a[i];
        if(i) pre[i] += pre[i-1];
    }
    cin >> p;
    
    vector<pair<intt,intt>> boo;
    for(intt i = 0; i < n; i++) {
        boo.push_back({(pre[i] - (p * i)), i});
    }
    sort(boo.begin(), boo.end());
    
    // for(intt i = 0; i < n; i++) {
    //     cout << boo[i].first << " " << boo[i].second << endl;
    // }

    intt ans = 0, idx = 1;
    update(1, 0, n - 1, boo[0].second);
    for(intt i = 1; i < n; i++) {
        while(idx < i && boo[i].fi - boo[idx].fi >= 0) {
            update(1, 0, n - 1, boo[idx].se);
            idx++;
        }
        ans += get(1,0,n-1,0,boo[i].se);
    }
    for(intt i = 0; i < n; i++) {
        if(pre[i] / (i + 1) >= p) {
            ++ans;
        }
    }
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    intt t = 1, buu = 1;
    // cin >> t;
    while(t--){
        // cout << "Case #" << buu++ << ": ";
        _();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...