oj.uz

Submission #942766

# Submission time Handle Problem Language Result Execution time Memory
942766 2024-03-11T04:15:09 Z ShadowShark Sum Zero (RMI20_sumzero) C++17
100 / 100
 608 ms 16600 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxN = 4e5 + 9;
int jump[9][maxN];
int *nxt;
pair<long long, int> *sum;

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

    int n;
    cin >> n;

    nxt = new int[n + 1];
    sum = new pair<long long, int>[n + 1];

    sum[0] = {0, 0};

    nxt[0] = n + 1;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum[i] = {sum[i - 1].first + x, i};
        nxt[i] = n + 1;
    }

    sort(sum, sum + n + 1);

    for (int i = 0; i <= n; i++) {
        //cout << sum[i].first << ' ' << sum[i].second << '\n';
        int j = i;
        while (j < n && sum[i].first == sum[j + 1].first) j++;

        for (int k = i; k < j; k++) nxt[sum[k].second + 1] = sum[k + 1].second;

        i = j;
    }

    delete[] sum;

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

    delete[] nxt;

    for (int i = 1; i <= 8; i++)
        for (int j = 0; j <= n + 1; j++)
            jump[i][j] = jump[i - 1][jump[i - 1][j]];

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        int ans = 0; l--;
        for (int i = 8; i >= 0; i--)
            while (jump[i][l] <= r) {
                l = jump[i][l];
                ans += 1 << i;
            }
        cout << ans << '\n';
    }

    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 4 ms 12888 KB Output is correct
5 Correct 3 ms 12888 KB Output is correct
6 Correct 3 ms 12888 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 4 ms 12888 KB Output is correct
5 Correct 3 ms 12888 KB Output is correct
6 Correct 3 ms 12888 KB Output is correct
7 Correct 61 ms 13732 KB Output is correct
8 Correct 42 ms 13484 KB Output is correct
9 Correct 62 ms 13688 KB Output is correct
10 Correct 60 ms 13936 KB Output is correct
11 Correct 43 ms 13484 KB Output is correct
12 Correct 65 ms 13636 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 4 ms 12888 KB Output is correct
5 Correct 3 ms 12888 KB Output is correct
6 Correct 3 ms 12888 KB Output is correct
7 Correct 61 ms 13732 KB Output is correct
8 Correct 42 ms 13484 KB Output is correct
9 Correct 62 ms 13688 KB Output is correct
10 Correct 60 ms 13936 KB Output is correct
11 Correct 43 ms 13484 KB Output is correct
12 Correct 65 ms 13636 KB Output is correct
13 Correct 608 ms 16424 KB Output is correct
14 Correct 206 ms 16160 KB Output is correct
15 Correct 580 ms 16600 KB Output is correct
16 Correct 521 ms 16448 KB Output is correct
17 Correct 234 ms 16056 KB Output is correct
18 Correct 545 ms 16560 KB Output is correct