Submission #1283768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283768		canhnam357	Sum Zero (RMI20_sumzero)	C++20	61 / 100	524 ms	32892 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define N 400000
#define LG 12
int st[N][LG], a[N];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < LG; j++) {
                st[i][j] = n;
            }
        }
        map<long long, int> mp;
        mp[0] = -1;
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += a[i];
            if (mp.count(sum)) {
                st[mp[sum] + 1][0] = i;
            }
            mp[sum] = i;
        }
        for (int i = n - 2; i >= 0; i--) {
            st[i][0] = min(st[i][0], st[i + 1][0]);
        }
        for (int j = 1; j < LG; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                if (st[i][j - 1] + 1 < n) {
                    st[i][j] = st[st[i][j - 1] + 1][j - 1];
                }
            }
            for (int i = n - 2; i >= 0; i--) {
                st[i][j] = min(st[i][j], st[i + 1][j]);
            }
        }
        int q;
        cin >> q;
        while (q--) {
            int l, r;
            cin >> l >> r;
            l--, r--;
            int ans = 0;
            for (int i = LG - 1; i >= 0; i--) {
                while (l <= r && st[l][i] <= r) {
                    ans += (1 << i);
                    l = st[l][i] + 1;
                }
            }
            cout << ans << '\n';
        }
    return 0;
}

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