oj.uz

Submission #862001

# Submission time Handle Problem Language Result Execution time Memory
862001 2023-10-17T10:57:34 Z sleepntsheep Sum Zero (RMI20_sumzero) C++17
100 / 100
 204 ms 19556 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 3 ms 4696 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 4 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 3 ms 4696 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 4 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 41 ms 6504 KB Output is correct
8 Correct 38 ms 6760 KB Output is correct
9 Correct 46 ms 5408 KB Output is correct
10 Correct 41 ms 6500 KB Output is correct
11 Correct 36 ms 6264 KB Output is correct
12 Correct 42 ms 5424 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 3 ms 4696 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 4 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 41 ms 6504 KB Output is correct
8 Correct 38 ms 6760 KB Output is correct
9 Correct 46 ms 5408 KB Output is correct
10 Correct 41 ms 6500 KB Output is correct
11 Correct 36 ms 6264 KB Output is correct
12 Correct 42 ms 5424 KB Output is correct
13 Correct 188 ms 12160 KB Output is correct
14 Correct 173 ms 13196 KB Output is correct
15 Correct 193 ms 14676 KB Output is correct
16 Correct 203 ms 19556 KB Output is correct
17 Correct 179 ms 18920 KB Output is correct
18 Correct 204 ms 14684 KB Output is correct