Submission #475951

#	Time	Username	Problem	Language	Result	Execution time	Memory
475951		Alexandruabcde	Sum Zero (RMI20_sumzero)	C++14	61 / 100	564 ms	28008 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

//ifstream f ("sumzero.in");
//ofstream g ("sumzero.out");

constexpr int NMAX = 1e6+5;
typedef long long LL;

int N;
int Root;

int L, R[NMAX];
int V[NMAX];
map <LL, int> mp;
int First[NMAX];
int Last[NMAX];
int prev_Question[NMAX];
int Question[NMAX];

void Read () {
    cin >> N;

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

void Precalculare () {
    Root = N + 2;
    First[N+2] = N+1;
    Last[N+2] = N+1;

    LL suff = 0;
    mp[0] = N;
    int val = N+1;

    for (int i = N; i >= 1; -- i ) {
        suff += 1LL * V[i];
        int ind = mp[suff];

        if (ind != 0)
            if (ind < val) {
                val = ind;
                First[val+1] = i;
            }

        Last[val+1] = i;
        mp[suff] = i-1;
    }

    mp.clear();
}

vector <int> D;

void Dfs (int Node) {
    if (Node == 0) return;

    D.push_back(Node);

    int q = Question[Node];

    while (q != 0) {
        int val = R[q]+1;

        int st = 0, dr = D.size()-1;
        int pos = 0;

        while (st <= dr) {
            int mij = (st + dr) / 2;

            if (D[mij] > val) {
                pos = mij;
                st = mij + 1;
            }
            else dr = mij - 1;
        }

        ++ pos;
        V[q] = (D.size()-1) - pos;

        q = prev_Question[q];
    }

    for (int i = First[Node]; i >= Last[Node]; -- i )
        Dfs(i);

    D.pop_back();
}

int Q;

void Solve () {
    cin >> Q;

    for (int i = 1; i <= Q; ++ i ) {
        cin >> L >> R[i];

        prev_Question[i] = Question[L];
        Question[L] = i;
    }

    Dfs(Root);

    for (int i = 1; i <= Q; ++ i )
        cout << V[i] << '\n';
}

int main () {
    Read();

    Precalculare();

    Solve();

    return 0;
}

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