Submission #862001

#	Time	Username	Problem	Language	Result	Execution time	Memory
862001		sleepntsheep	Sum Zero (RMI20_sumzero)	C++17	100 / 100	204 ms	19556 KiB

sumzero

#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;

#define N 400005

int n, q, P_[N], *P = P_+1, J_[N], *J = J_+1, D_[N], *D = D_+1;

int qry(int l, int r)
{
    int d = r;
    while (P[r] >= l-1 && r) r = (J[r] >= l-1 ? J[r] : P[r]);
    return D[d] - D[r];
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    {
        ll p = 0, u = -1, x;
        unordered_map<int, int> mp = {{0,0}};
        J[-1] = -1;
        P[0] = J[0] = -1;
        for (int i = 1; i <= n; ++i)
        {
            cin >> x;
            if (mp.count(p += x)) u = max(u, 1ll*mp[p]);
            P[i] = u, D[i] = D[u] + 1;
            if (D[u] - D[J[u]] == D[J[u]] - D[J[J[u]]]) J[i] = J[J[u]];
            else J[i] = u;
            mp[p] = i;
        }
    }

    cin >> q;
    for (int l, r; q--; ) cin >> l >> r, cout << qry(l, r) << '\n';

    return 0;
}

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