Submission #1316224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316224		sefat	Sum Zero (RMI20_sumzero)	C++20	0 / 100	2 ms	824 KiB

sumzero

#pragma GCC optimize("O3,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

// ----------- Constants ------------
static const ll INF = (ll)1e18;

// ----------- Main Solve Function ------------
void solve() {
    int n;
    cin >> n;

    vector<ll> a(n + 1), pref(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }

    // compute LOG dynamically
    int LOG = 1;
    while ((1LL << LOG) <= n) LOG++;

    // flat jump table: LOG * (n+2)
    vector<int> jump(LOG * (n + 2), -1);
    auto J = [&](int j, int i) -> int& {
        return jump[j * (n + 2) + i];
    };

    map<ll, int> mp;

    // base case
    J(0, n) = n + 1;
    mp[pref[n]] = n;

    // build jump[0][i]
    for (int i = n - 1; i >= 1; i--) {
        auto it = mp.find(pref[i - 1]);
        if (it == mp.end()) {
            J(0, i) = J(0, i + 1);
        } else {
            int pos = it->second;
            if (J(0, i + 1) == -1)
                J(0, i) = pos;
            else
                J(0, i) = min(J(0, i + 1), pos);
        }
        mp[pref[i]] = i;
    }

    // binary lifting
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= n; i++) {
            int nxt = J(j - 1, i);
            if (nxt != -1 && nxt <= n + 1) {
                J(j, i) = J(j - 1, nxt);
            }
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;

        int cur = l;
        ll ans = 0;

        for (int j = LOG - 1; j >= 0; j--) {
            int nxt = J(j, cur);
            if (nxt != -1 && nxt <= r) {
                ans += (1LL << j);
                cur = nxt;
            }
        }

        cout << ans << '\n';
    }
}

// ----------- Main Function ------------
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

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