Submission #475409

#	Time	Username	Problem	Language	Result	Execution time	Memory
475409		Alexandruabcde	Sum Zero (RMI20_sumzero)	C++14	0 / 100	9 ms	10444 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

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 step = 0;
int Size[NMAX];
int Max_Son[NMAX];
int poz[NMAX];
int ID[NMAX];
int aux = 0;
int First[NMAX];

struct AINT {
    int *A;

    AINT(int size): A(new int [4*size]) {
        for (int i = 0; i < 4*size; ++ i )
            A[i] = 0;
    }

    void Update (int nod, int a, int b, int pos, int val) {
        if (a == b) {
            A[nod] = val;
            return;
        }

        int mij = (a + b) / 2;

        if (pos <= mij) Update(2*nod, a, mij, pos, val);
        else Update(2*nod+1, mij+1, b, pos, val);

        A[nod] = max(A[2*nod], A[2*nod+1]);
    }

    int Interior (int nod, int a, int b, int qa, int qb, int val) {
        int value = A[nod];

        if (value > val) {
            if (a == b) return -1;

            int mij = (a + b) / 2;
            int ans_st = A[2*nod];
            int ans_dr = A[2*nod+1];

            if (val >= ans_dr) return max(ans_dr, Interior(2*nod, a, mij, qa, qb, val));
            return Interior(2*nod, a, mij, qa, qb, val);
        }

        return A[nod];
    }

    int Query (int nod, int a, int b, int qa, int qb, int val) {
        if (qa <= a && b <= qb)
            return Interior(nod, a, b, qa, qb, val);

        int mij = (a + b) / 2;
        int ans_1 = 0, ans_2 = 0;

        if (qa <= mij) ans_1 = Query(2*nod, a, mij, qa, qb, val);
        if (mij < qb) ans_2 = Query(2*nod+1, mij+1, b, qa, qb, val);

        if (ans_1 > val && ans_2 > val) return -1;
        if (ans_1 > val) return ans_2;
        if (ans_2 > val) return ans_1;
        return max(ans_1, ans_2);
    }
};

AINT* Arbore;

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

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

void Precalculare () {
    while ((1<<step) <= N) ++ step;
    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 chains = 1;
void Split (int Node) {
    ID[Node] = chains;
    poz[Node] = ++ aux;

    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);

    Arbore = new AINT(4*(N+4));

    for (int i = 1; i <= N+2; ++ i )
        Arbore->Update(1, 1, N, poz[i], i);
}

int Query (int start, int Finish) {
    return 0;
}

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;
}

Compilation message (stderr)

sumzero.cpp: In member function 'int AINT::Interior(int, int, int, int, int, int)':
sumzero.cpp:51:17: warning: unused variable 'ans_st' [-Wunused-variable]
   51 |             int ans_st = A[2*nod];
      |                 ^~~~~~

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