Submission #1136195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136195		BuiDucManh123	Sum Zero (RMI20_sumzero)	C++17	61 / 100	302 ms	40240 KiB

sumzero

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int, int>
using namespace std;

const int lg = 20;

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

    int n, q;
    cin >> n;

    vector<vector<int>> f(lg, vector<int>(n + 1, -1)); // Use vector for memory efficiency
    unordered_map<ll, int> check;
    ll sum = 0;

    for (int i = 1; i <= n; ++i) {
        int a;
        cin >> a;
        sum += a;

        if (!check.count(sum) && sum != 0) {
            check[sum] = -1;
        }
        f[0][i] = max(check[sum], f[0][i - 1]);
        check[sum] = i;
    }

    // Clear the map after usage
    check.clear();

    // Build sparse table
    for (int i = 1; i < lg; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (f[i - 1][j] != -1) {
                f[i][j] = f[i - 1][f[i - 1][j]];
            }
        }
    }

    // Answer queries
    cin >> q;
    while (q--) {
        int l, r, ans = 0;
        cin >> l >> r;

        for (int i = lg - 1; i >= 0; --i) {
            if (f[i][r] >= l - 1) {
                ans += (1 << i);
                r = f[i][r];
            }
        }
        cout << ans << "\n";
    }

    return 0;
}

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