Submission #1033387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033387		Raul_A	Sum Zero (RMI20_sumzero)	C++14	61 / 100	1059 ms	20508 KiB

sumzero

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define pii pair<int, int>
#define tpl tuple<int, int, int>
#define OO LLONG_MAX / 2
using namespace std;

int N;
vector<int> v,freq, nxt, jump, dp;
vector<ll> M, suff;

/*
    1 2 -3 0 1 -4 3 2 -1 1
    0 0 1 2 3 4 4 5 5 6 7

    1 2 -3
    1 2 -3 0
    0
    2 -3 0 1
    0 1 -4 3
    2 -3 0 1 -4 3 2 -1
    -1 1
*/

void read()
{
    cin >> N;

    v.resize(N + 1, 0);

    for (int i = 1; i <= N; i++)
        cin >> v[i];
}

void init()
{
    suff.resize(N + 5), M.resize(N + 5);
    for (int i = N; i >= 1; i--)
    {
        suff[i] = suff[i + 1] + v[i];
        M.eb(suff[i]);
    }

    sort(M.begin(), M.end());
    M.erase(unique(M.begin(), M.end()), M.end());

    freq.resize(N + 5);
    nxt.resize(N + 5);

    freq[upper_bound(M.begin(), M.end(), 0) - M.begin()] = N + 1;
    
    int pos = N + 2;
    for (int i = N; i >= 0; i--)
    {
        suff[i] = upper_bound(M.begin(), M.end(), suff[i]) - M.begin();

        if (freq[suff[i]])
            pos = min(pos, freq[suff[i]]);

        nxt[i] = pos;

        freq[suff[i]] = i;
    }

    jump.resize(N + 5), dp.resize(N + 5);
    for (int i = N; i >= 1; i--)
    {
        int father = nxt[i];
        jump[i] = father;
        dp[i] = 1;
        if (jump[jump[father]] - jump[father] == jump[father] - father)
        {
            jump[i] = jump[jump[father]];
            dp[i] = dp[father] + dp[jump[father]] + 1;
        }
    }
}

void queries()
{
    int Q, l, r;
    cin >> Q;
    while (Q--)
    {
        cin >> l >> r;

        int ans = 0;
        while (l <= r)
        {
            if (jump[l] <= r + 1)
            {
                ans += dp[l];
                l = jump[l];
            }
            else
            {
                if (nxt[l] <= r + 1)
                {
                    ++ans;
                    l = nxt[l];
                }
                else
                    l = r + 1;
            }
        }

        cout << ans << '\n';
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    read();
    init();
    queries();
    exit(0);
}

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