Submission #857121

#	Time	Username	Problem	Language	Result	Execution time	Memory
857121		busamate	Sum Zero (RMI20_sumzero)	C++14	22 / 100	78 ms	22608 KiB

sumzero

#include <iostream>
#include <set>
#include <algorithm>

using namespace std;

long long N, Q, hol, o, tart;
int t[400001];
int ki[400000];
int aa[400000];
int bb[400000];
int f[400001][19];

set<pair<long long, int>> szet;
set<int> veg;

void solve(int x, int ki)
{
    int y = aa[ki];
    if (t[x] < y)
    {
        aa[ki] = 0;
        return;
    }

    int ret = 0;
    for (int i = 18; i >= 0; i--)
    {
        if (f[x][i] != -1 && y <= t[f[x][i]])
        {
            ret += (1 << i);
            x = f[x][i];
        }
    }
    aa[ki] = ret + 1;
}

bool kis(int x, int y)
{
    return bb[x] < bb[y];
}

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

    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> t[i];
        for (int j = 0; j < 19; j++)
            f[i][j] = -1;
    }
    cin >> Q;
    for (int i = 0; i < Q; i++)
    {
        cin >> aa[i] >> bb[i];
        ki[i] = i;
    }
    sort(ki, ki + Q, kis);

    szet.insert({0, -0});
    veg.insert(0);
    int last = 0;
    for (int i = 1; i <= N; i++)
    {
        o += (long long)t[i];
        auto it = szet.lower_bound({o, -2 * N});
        if (it != szet.end() && (*it).first == o && -(*it).second + 1 > last)
        {
            last = -(*it).second + 1;
            auto it2 = veg.lower_bound(last);
            it2--;
            int apa = (*it2);

            f[i][0] = apa;

            for (int j = 1; j < 19 && f[f[i][j - 1]][j - 1] != -1; j++)
            {
                f[i][j] = f[f[i][j - 1]][j - 1];
            }

            t[i] = last;
            veg.insert(i);
        }

        int utso = (*veg.rbegin());
        while (tart < Q && bb[ki[tart]] == i)
        {
            solve(utso, ki[tart]);
            tart++;
        }

        szet.insert({o, -i});
    }

    for (int i = 0; i < Q; i++)
        cout << aa[i] << '\n';

    return 0;
}

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