제출 #475304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
475304		Alexandruabcde	Sum Zero (RMI20_sumzero)	C++14	61 / 100	760 ms	50092 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

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

int N;
int V[NMAX];
int Q;
int Next[20][NMAX];

map <LL, int> mp;

int step = 0;

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 () {
    Next[0][N+1] = 1000000000;
    while ((1<<step) <= N) ++ step;

    LL suff = 0;
    mp[0] = N;

    for (int i = N; i >= 1; -- i ) {
        Next[0][i] = Next[0][i+1];

        suff += 1LL * V[i];
        int ind = mp[suff];

        if (ind != 0) Next[0][i] = min(Next[0][i], ind);

        mp[suff] = i-1;
    }

    for (int L = 1; (1<<L) <= N; ++ L ) {
        Next[L][N+1] = 1000000000;
        for (int i = 1; i <= N; ++ i ) {
            if (Next[L-1][i] >= N) Next[L][i] = 1000000000;
            else Next[L][i] = Next[L-1][Next[L-1][i]+1];
        }
    }
}

int Query (int start, int Finish) {
    int ans = 0;
    for (int i = step-1; i >= 0; -- i ) {
        if (Next[i][start] > Finish) continue;

        ans += (1<<i);
        start = Next[i][start]+1;
    }

    return ans;
}

void Solve () {
    cin >> Q;

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

        cin >> L >> R;

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

int main () {
    Read();

    Precalculare();

    Solve();

    return 0;
}

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