Submission #857154

#	Time	Username	Problem	Language	Result	Execution time	Memory
857154		busamate	Sum Zero (RMI20_sumzero)	C++14	100 / 100	650 ms	17584 KiB

sumzero

#include <iostream>
#include <unordered_map>

using namespace std;

const int step = 400;

long long N, Q, hol, o, tart, a, b, megy, mit;
int t[400001];
int apa[400001];
int f[400001];
int veg[400001];

unordered_map<long long, int> szet;

int bi(int x, int y)
{
    if (veg[y] < mit)
        return y + 1;
    if (x == y)
        return x;

    int fel = (x + y) / 2;
    if (mit <= veg[fel])
        return bi(x, fel);
    return bi(fel + 1, y);
}

int solve(int x)
{
    int y = a;
    if (t[x] < y)
    {
        return 0;
    }

    int ret = 0;
    while (f[x] != -1 && y <= t[f[x]])
    {
        ret += step;
        x = f[x];
    }

    while (x != 0 && y <= t[apa[x]])
    {
        ret++;
        x = apa[x];
    }

    return ret + 1;
}

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];
        f[i] = -1;
    }
    f[0] = -1;

    szet.insert({0, 0});
    veg[megy++] = 0;
    int last = 0;
    for (int i = 1; i <= N; i++)
    {
        o += (long long)t[i];
        auto it = szet.find(o);
        if (it != szet.end())
        {
            if(szet[o]+1 > last){
                last = szet[o] + 1;

                mit = last;
                int hol = bi(0, megy - 1) - 1;

                apa[i] = veg[hol];

                f[i] = i;
                for (int cnt = 0; cnt < step; cnt++)
                {
                    if (f[i] == 0)
                    {
                        f[i] = -1;
                        break;
                    }
                    f[i] = apa[f[i]];
                }

                t[i] = last;
                veg[megy++] = i;
            }
            szet[o] = i;
        }
        else
        {
            szet.insert({o, i});
        }
    }

    cin >> Q;
    for (int i = 0; i < Q; i++)
    {
        cin >> a >> b;
        mit = b + 1;
        int hol = bi(0, megy - 1) - 1;
        cout << solve(veg[hol]) << '\n';
    }

    return 0;
}

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