Submission #1026145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026145		NValchanov	Sum Zero (RMI20_sumzero)	C++17	100 / 100	187 ms	19060 KiB

sumzero

#include <iostream>
#include <unordered_map>

#define endl '\n'

using namespace std;

typedef long long ll;

const int MAXN = 4e5 + 10;
const int MAXQ = 4e5 + 10;
const int MAXLOG = 18;

int n, q;
int a[MAXN];
int lift[MAXN];
pair < int, int > queries[MAXQ];
int ans[MAXN];

unordered_map < ll, int > sums;

void read()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    cin >> q;
    for(int i = 1; i <= q; i++)
    {
        cin >> queries[i].first >> queries[i].second;
    }
}

void fill_nxt()
{
    int minpos = MAXN - 1;
    ll cursum = 0;

    for(int i = n + 1; i >= 1; i--)
    {
        cursum += a[i];

        if(sums.find(cursum) != sums.end())
            minpos = min(minpos, sums[cursum]);

        sums[cursum] = i;
        a[i] = minpos;
    }
}

void solve()
{
    for(int k = MAXLOG - 1; k >= 0; k--)
    {
        for(int i = 1; i <= n + 1; i++)
        {
            lift[i] = a[i];
        }
        lift[MAXN - 1] = MAXN - 1;

        for(int j = 1; j <= k; j++)
        {
            for(int i = 1; i <= n + 1; i++)
            {
                lift[i] = lift[lift[i]];
            }
            lift[MAXN - 1] = lift[lift[MAXN - 1]];
        }

        for(int i = 1; i <= q; i++)
        {
            if(lift[queries[i].first] <= queries[i].second + 1)
            {
                ans[i] += (1 << k);
                queries[i].first = lift[queries[i].first];
            }
        }
    }
}

void print()
{
    for(int i = 1; i <= q; i++)
    {
        cout << ans[i] << endl;
    }
    cout << endl;
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    read();
    fill_nxt();
    solve();
    print();

    return 0;
}

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