Submission #1137924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137924		SyedSohaib_123	Sum Zero (RMI20_sumzero)	C++20	0 / 100	6 ms	576 KiB

sumzero

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

#define append push_back
#define int long long

const int N = 4e5 + 10, LG = 25;
int mod = 998244353;

int a[N], dp[N];

void solve(int tst) {
    int n;
    cin >> n;

    // Compute prefix sums
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1];
    }

    map<int, int> last;
    dp[n + 1] = n + 1; // Boundary condition

    // Compute `dp` and track last occurrences
    for (int i = n; i >= 1; i--) {
        dp[i] = dp[i + 1];
        if (last.count(a[i - 1])) {
            dp[i] = min(dp[i], last[a[i - 1]]);
        }
        last[a[i - 1]] = i; // Update last occurrence of the prefix sum
    }

    int q;
    cin >> q;

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

        int ans = 0;
        while (l <= r) {
            if (dp[l] > r) break;
            l = dp[l] + 1;
            ans++;
        }
        cout << ans << endl;
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; i++) {
        solve(i);
    }
}

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