oj.uz

Submission #398522

# Submission time Handle Problem Language Result Execution time Memory
398522 2021-05-04T13:10:37 Z model_code Sum Zero (RMI20_sumzero) C++17
100 / 100
 561 ms 19920 KB 
/**
* user:  apostol-089
* fname: Daniel Ilie
* lname: Apostol
* task:  SumZero
* score: 100.0
* date:  2020-12-04 10:14:48.418363
*/
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

const int N = 4e5 + 10, K = 5;
unordered_map <ll, int> mp;
int go[1 + N];
int nxt[1 + N][K]; /// what position we are on
int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n;
    cin >> n;
    ll sum = 0;
    for (int i = 0; i <= n; i++)
        go[i] = -1;
    for (int i = 0; i <= n; i++) {
        if (i > 0) {
            int x;
            cin >> x;
            sum += x;
        }
        if (mp.count (sum))
            go[mp[sum]] = i;
        mp[sum] = i;
    }
    mp.clear ();
    for (int i = 0; i < K; i++)
        for (int j = 0; j <= n; j++)
            nxt[j][i] = -1;

    int mn = n + 1;
    for (int i = n; i >= 0; i--) {
        if (go[i] != -1)
            mn = min (mn, go[i]);
        if (mn <= n)
            nxt[i][0] = mn;
    }
    for (int k = 1; k < K; k++)
        for (int i = 0; i <= n; i++) {
            int x = i;
            for (int j = 0; j < 16; j++) {
                if (x != -1)
                    x = nxt[x][k - 1];
            }
            nxt[i][k] = x;
        }
    /// no consecutive are good
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        int now = x - 1;
        int ans = 0;
        int k = K - 1;
        while (k >= 0) {
            if (nxt[now][k] > 0 && nxt[now][k] <= y) {
                now = nxt[now][k];
                ans += (1 << (4 * k));
            }
            else
                k--;
        }
        cout << ans << "\n";
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 4 ms 544 KB Output is correct
3 Correct 4 ms 588 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 4 ms 560 KB Output is correct
6 Correct 4 ms 588 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 4 ms 544 KB Output is correct
3 Correct 4 ms 588 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 4 ms 560 KB Output is correct
6 Correct 4 ms 588 KB Output is correct
7 Correct 95 ms 4828 KB Output is correct
8 Correct 75 ms 5056 KB Output is correct
9 Correct 111 ms 3576 KB Output is correct
10 Correct 88 ms 4796 KB Output is correct
11 Correct 75 ms 4620 KB Output is correct
12 Correct 93 ms 3700 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 4 ms 544 KB Output is correct
3 Correct 4 ms 588 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 4 ms 560 KB Output is correct
6 Correct 4 ms 588 KB Output is correct
7 Correct 95 ms 4828 KB Output is correct
8 Correct 75 ms 5056 KB Output is correct
9 Correct 111 ms 3576 KB Output is correct
10 Correct 88 ms 4796 KB Output is correct
11 Correct 75 ms 4620 KB Output is correct
12 Correct 93 ms 3700 KB Output is correct
13 Correct 524 ms 18764 KB Output is correct
14 Correct 489 ms 19656 KB Output is correct
15 Correct 552 ms 12608 KB Output is correct
16 Correct 557 ms 19920 KB Output is correct
17 Correct 401 ms 18084 KB Output is correct
18 Correct 561 ms 12404 KB Output is correct