Submission #475933

#	Time	Username	Problem	Language	Result	Execution time	Memory
475933		Alexandruabcde	Sum Zero (RMI20_sumzero)	C++14	61 / 100	380 ms	36196 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

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

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

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

int Dad[NMAX];
int order[NMAX];
int ID[NMAX];
int poz[NMAX];
int First[IDMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;

    for (int i = 1; i <= N; ++ i )
        cin >> order[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 * order[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) {
    ID[Node] = 1;

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

int aux = 0;
int chains = 1;

void Split (int Node) {
    int Max_Son = 0;
    for (auto it : G[Node])
        if (Max_Son == 0 || ID[Max_Son] < ID[it])
            Max_Son = it;

    ID[Node] = chains;
    poz[Node] = ++ aux;
    order[poz[Node]] = Node;

    if (Max_Son == 0) return;

    Split(Max_Son);

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

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

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

    for (int i = N+2; i >= 1; -- i )
        G[i].clear();
}

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 () {
    cin >> Q;

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

        cin >> L >> R;

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

int main () {
    Read();

    Precalculare();
    Do_HeavyPath();

    Solve();

    return 0;
}

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