Submission #1283764

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

sumzero

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define N 200000
#define LG 18
int st[N][LG], a[2 * N];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    if (n <= N) {
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) {
            for (int j = 0; i + (1 << j) <= n; 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--) {
                if (l + (1 << i) <= n && st[l][i] <= r) {
                    ans += (1 << i);
                    l = st[l][i] + 1;
                }
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

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