oj.uz

Submission #857154

# Submission time Handle Problem Language Result Execution time Memory
857154 2023-10-05T13:05:20 Z busamate Sum Zero (RMI20_sumzero) C++14
100 / 100
 650 ms 17584 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4444 KB Output is correct
2 Correct 4 ms 4692 KB Output is correct
3 Correct 5 ms 4700 KB Output is correct
4 Correct 4 ms 4700 KB Output is correct
5 Correct 4 ms 4700 KB Output is correct
6 Correct 4 ms 4752 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4444 KB Output is correct
2 Correct 4 ms 4692 KB Output is correct
3 Correct 5 ms 4700 KB Output is correct
4 Correct 4 ms 4700 KB Output is correct
5 Correct 4 ms 4700 KB Output is correct
6 Correct 4 ms 4752 KB Output is correct
7 Correct 106 ms 7088 KB Output is correct
8 Correct 111 ms 7552 KB Output is correct
9 Correct 109 ms 6192 KB Output is correct
10 Correct 106 ms 7084 KB Output is correct
11 Correct 111 ms 6832 KB Output is correct
12 Correct 106 ms 5876 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4444 KB Output is correct
2 Correct 4 ms 4692 KB Output is correct
3 Correct 5 ms 4700 KB Output is correct
4 Correct 4 ms 4700 KB Output is correct
5 Correct 4 ms 4700 KB Output is correct
6 Correct 4 ms 4752 KB Output is correct
7 Correct 106 ms 7088 KB Output is correct
8 Correct 111 ms 7552 KB Output is correct
9 Correct 109 ms 6192 KB Output is correct
10 Correct 106 ms 7084 KB Output is correct
11 Correct 111 ms 6832 KB Output is correct
12 Correct 106 ms 5876 KB Output is correct
13 Correct 650 ms 14972 KB Output is correct
14 Correct 570 ms 17432 KB Output is correct
15 Correct 618 ms 9552 KB Output is correct
16 Correct 609 ms 17584 KB Output is correct
17 Correct 545 ms 14396 KB Output is correct
18 Correct 610 ms 9528 KB Output is correct