Submission #1214745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214745		vukhacminh	Sum Zero (RMI20_sumzero)	C++20	61 / 100	369 ms	38268 KiB

sumzero

/**
*    Author :  Vu Khac Minh
**/
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 4e5 + 1;
const int LG = 13;

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

    int n, nquery;
    cin >> n;

    int* a = new int[n + 2]; 
    pair<ll, int>* b = new pair<ll, int>[n + 1];
    int** nxt = new int*[n + 2];
    for (int i = 0; i <= n + 1; i++)
        nxt[i] = new int[LG];

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

    sort(b, b + n + 1);

    for (int i = 0; i < n; i++) {
        if (b[i].first == b[i + 1].first) a[b[i].second] = b[i + 1].second;
        else a[b[i].second] = n + 1;
    }
    a[b[n].second] = n + 1;

    for (int i = 0; i <= n; i++) nxt[i][0] = a[i];
    for (int j = 0; j < LG; j++) nxt[n + 1][j] = n + 1;

    for (int i = n; i >= 0; i--) {
        nxt[i][0] = min(nxt[i][0], nxt[i + 1][0]);
        for (int j = 1; j < LG; j++)
            nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
    }

    cin >> nquery;
    while (nquery--) {
        int l, r, res = 0;
        cin >> l >> r;
        l--;
        for (int i = LG - 1; i >= 0; i--) {
            while (nxt[l][i] <= r) {
                l = nxt[l][i];
                res += (1 << i);
            }
        }
        cout << res << '\n';
    }

    delete[] a;
    delete[] b;
    for (int i = 0; i <= n + 1; i++)
        delete[] nxt[i];
    delete[] nxt;

    return 0;
}

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