Submission #1267885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267885		ngunguoi45	Vudu (COCI15_vudu)	C++17	140 / 140	416 ms	36020 KiB

vudu

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
using pii = pair<int,int>;

const int maxn = (int)1e6+5;

int n;
int a[maxn];
ll p;

namespace sub1 {
    ll ans = 0;
    ll pref[maxn];
    bool check () {
        return (n <= 10000);
    }
    void solve () {
        for (int i = 1;i <= n; i++) {
            pref[i] = pref[i-1] + a[i];
        }
        for (int l = 1; l <= n; l++) {
            for (int i = 1; i+l-1 <= n; i++) {
                if (pref[i+l-1] - pref[i-1] >= p*l) ans++;
            }
        }
        cout << ans << "\n";
    }
}

namespace sub2 {
    struct Segtree {
        vector<int> node;
        Segtree (int n): node (4*n+5) {}
        void update (int v, int l, int r, int pos, int val) {
            if (pos > r || pos < l) return;
            if (l == r) {
                node[v] += val;
                return;
            }
            int mid = (l + r) / 2;
            update (v<<1, l, mid, pos, val);
            update (v<<1|1, mid+1, r, pos, val);
            node[v] = node[v<<1] + node[v<<1|1];
        }
        int get (int v, int l, int r, int tl, int tr) {
            if (tl > r || tr < l) return 0;
            if (tl <= l && r <= tr) return node[v];
            int mid = (l + r) / 2;
            return get(v<<1, l, mid, tl, tr) + get(v<<1|1, mid+1, r, tl, tr);
        }
    };
    ll ans = 0;
    vector<ll> pref(maxn), b;
    Segtree ST(maxn);

    void init_compress () {
        sort (b.begin(), b.end());
        b.resize(distance(b.begin(), unique(b.begin(), b.end())));
        for (int i = 0;i <= n; i++) {
            auto it = upper_bound (b.begin(), b.end(), pref[i]);
            pref[i] = it - b.begin();
        }
    }
    void solve () {
        pref[0] = -p;
        b.push_back(pref[0]);
        for (int i = 1;i <= n; i++) {
            pref[i] = pref[i-1] + a[i] - p;
            b.push_back(pref[i]);
        }
        init_compress();
        for (int i = n;i >= 1; i--) {
            ST.update (1,1,maxn,pref[i], 1);
            ans += ST.get(1,1,maxn,pref[i-1],maxn);
        }
        cout << ans << "\n";
    }
}

void read_and_prep() {
    cin >> n;
    for (int i = 1;i <= n; i++) cin >> a[i];
    cin >> p;
}

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

    read_and_prep();
    if (sub1::check()) sub1::solve();
    else sub2::solve();
    return 0;
}

• Subtask 1: 140 / 140