Submission #1312443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312443		seriousgrey	Sum Zero (RMI20_sumzero)	C++20	22 / 100	74 ms	22960 KiB

sumzero

#pragma GCC optimize("O3,unroll-loops,no-stack-protector,fast-math")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const int LOG = 20; // 2^20 = 1,048,576 > 4e5

    int n;
    if (!(cin >> n)) return 0;
    vi c(n);
    for (int i = 0; i < n; ++i) cin >> c[i];

    // Build prefix sums
    vector<ll> pref(n);
    for (int i = 0; i < n; ++i) {
        pref[i] = c[i] + (i ? pref[i-1] : 0LL);
    }

    // Coordinate-compress values: include 0 and all pref[i]
    vector<ll> vals;
    vals.reserve(n+1);
    vals.push_back(0LL);
    for (int i = 0; i < n; ++i) vals.push_back(pref[i]);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int m = (int)vals.size();

    // positions for each compressed value
    vector<vector<int>> posList(m);
    // push -1 for prefix = 0
    int idx0 = int(lower_bound(vals.begin(), vals.end(), 0LL) - vals.begin());
    posList[idx0].push_back(-1);
    for (int i = 0; i < n; ++i) {
        int id = int(lower_bound(vals.begin(), vals.end(), pref[i]) - vals.begin());
        posList[id].push_back(i);
    }

    // nxt[i] = earliest j >= i with pref[j] == pref[i-1] (or n if none)
    vi nxt(n, n);
    for (int i = 0; i < n; ++i) {
        ll need = (i ? pref[i-1] : 0LL);
        int id = int(lower_bound(vals.begin(), vals.end(), need) - vals.begin());
        auto &v = posList[id];
        auto it = lower_bound(v.begin(), v.end(), i);
        nxt[i] = (it == v.end() ? n : *it);
    }

    // best[i] = minimal end among starts >= i
    vi best(n+1, n);
    for (int i = n-1; i >= 0; --i) best[i] = min(nxt[i], best[i+1]);

    // go[i] = position after taking that earliest-finishing interval (end+1), or n
    vi go(n+1, n);
    for (int i = 0; i < n; ++i) if (best[i] != n) go[i] = best[i] + 1;
    go[n] = n;

    // Binary lifting tables: pos[k][i] = position after applying 2^k greedy picks starting at i
    // cnt[k][i] = actual number of real segments represented by that 2^k-block
    vector<vi> pos(LOG, vi(n+1, n));
    vector<vi> cnt(LOG, vi(n+1, 0));

    for (int i = 0; i <= n; ++i) pos[0][i] = go[i];
    for (int i = 0; i < n; ++i) cnt[0][i] = (best[i] == n ? 0 : 1);
    cnt[0][n] = 0;

    for (int k = 1; k < LOG; ++k) {
        for (int i = 0; i <= n; ++i) {
            int mid = pos[k-1][i];
            pos[k][i] = (mid <= n ? pos[k-1][mid] : n);
            // cnt sums exact realized segments
            cnt[k][i] = cnt[k-1][i] + (mid <= n ? cnt[k-1][mid] : 0);
        }
    }

    int q; cin >> q;
    while (q--) {
        int l, r; cin >> l >> r;
        --l; --r;
        int p = l;
        int ans = 0;
        for (int k = LOG-1; k >= 0; --k) {
            if (p == n) break;
            int np = pos[k][p];
            // if this 2^k-block stays within range (end <= r) and actually contains segments
            if (np <= r + 1 && cnt[k][p] > 0) {
                ans += cnt[k][p];
                p = np;
            }
        }
        cout << ans << '\n';
    }

    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 0 / 39
• Subtask 3: 0 / 39