Submission #475916

#	Time	Username	Problem	Language	Result	Execution time	Memory
475916		Alexandruabcde	Sum Zero (RMI20_sumzero)	C++14	0 / 100	5 ms	9676 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

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

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

int N;
int V[NMAX];
vector <int> G[NMAX];
map <LL, int> mp;
int Dad[NMAX];
int Root;

int order[NMAX];
int Size[NMAX];
int Max_Son[NMAX];
int poz[NMAX];
int ID[NMAX];
int First[NMAX];

void Read () {
    f >> N;

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

void Precalculare () {
    Root = N + 2;
    G[N+2].push_back(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) val = min(val, ind);

        G[val+1].push_back(i);
        Dad[i] = val+1;
        mp[suff] = i-1;
    }
}

void Dfs_Initial (int Node) {
    Size[Node] = 1;

    for (auto it : G[Node]) {
        Dfs_Initial(it);
        Size[Node] += Size[it];

        if (Max_Son[Node] == 0 || Size[Max_Son[Node]] < Size[it])
            Max_Son[Node] = it;
    }
}

int aux = 0;
int chains = 1;

void Split (int Node) {
    ID[Node] = chains;
    poz[Node] = ++ aux;
    order[poz[Node]] = Node;

    if (Size[Node] == 1) return;

    Split(Max_Son[Node]);

    for (auto it : G[Node]) {
        if (it == Max_Son[Node]) continue;

        ++ chains;
        First[chains] = it;
        Split(it);
    }
}

void Do_HeavyPath () {
    Dfs_Initial(Root);
    First[1] = Root;
    Split(Root);
}

int Query (int start, int Finish) {
    int ans = 0;
    while (start < Finish) {
        if (First[ID[start]] <= Finish && Dad[First[ID[start]]] <= Finish) {
            ans += poz[start] - poz[First[ID[start]]] + 1;
            start = Dad[First[ID[start]]];
        }
        else {
            int st = poz[First[ID[start]]];
            int dr = poz[start];
            int pos = poz[First[ID[start]]]-1;
            while (st <= dr) {
                int mij = (st + dr) / 2;

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

            ans += (poz[start] - pos);
            break;
        }
    }

    return ans;
}

int Q;

void Solve () {
    f >> Q;

    for (; Q; -- Q ) {
        int L, R;

        f >> L >> R;

        g << Query(L, R+1) << '\n';
    }
}

int main () {
    Read();

    Precalculare();
    Do_HeavyPath();

    Solve();

    return 0;
}

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