Submission #475978

#	Time	Username	Problem	Language	Result	Execution time	Memory
475978		Alexandruabcde	Sum Zero (RMI20_sumzero)	C++14	61 / 100	541 ms	20924 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

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

constexpr int NMAX = 4e5+3;
typedef long long LL;

int N;
int Root;

int L, R[NMAX];
int V[NMAX];
int First[NMAX];
int Last[NMAX];
int prev_Question[NMAX];
int Question[NMAX];
int D[NMAX];
int vf = 0;

void Read () {
    cin >> N;

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

    for (int i = N; i >= 1; -- i )
        R[i] = R[i+1] + V[i];
    sort(R+1, R+N+1+1);

    int st = 1, dr = N+1;
    int ind = 0;
    while (st <= dr) {
        int mij = (st + dr) / 2;

        if (R[mij] == 0) {
            dr = mij - 1;
            ind = mij;
        }
        else if (R[mij] < 0) st = mij + 1;
        else if (R[mij] > 0) dr = mij - 1;
    }
    D[ind] = N;
}

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

    for (int i = N; i >= 1; -- i ) {
        suff += V[i];
        int st = 1, dr = N+1;
        int ind = 0;
        while (st <= dr) {
            int mij = (st + dr) / 2;

            if (R[mij] == suff) {
                dr = mij - 1;
                ind = mij;
            }
            else if (R[mij] < suff) st = mij + 1;
            else if (R[mij] > suff) dr = mij - 1;
        }

        int aux = D[ind];

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

        Last[val+1] = i;
        D[ind] = i-1;
    }
}

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

    D[++vf] = Node;

    int q = Question[Node];

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

        int st = 1, dr = vf;
        int pos = 1;

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

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

        ++ pos;
        V[q] = vf - pos;

        q = prev_Question[q];
    }

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

    --vf;
}

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