Submission #398522

#	Time	Username	Problem	Language	Result	Execution time	Memory
398522		model_code	Sum Zero (RMI20_sumzero)	C++17	100 / 100	561 ms	19920 KiB

sumzero

/**
* 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 / 22
• Subtask 2: 39 / 39
• Subtask 3: 39 / 39