Submission #488328

#	Time	Username	Problem	Language	Result	Execution time	Memory
488328		boris_mihov	Sum Zero (RMI20_sumzero)	C++17	61 / 100	522 ms	47892 KiB

sumzero

#include <iostream>
#include <unordered_map>
using namespace std;
const int maxn = 4e5+10, maxlog = 19;

int sparse[maxlog][maxn];
int jump[maxn];
int a[maxn], n, q;

void build_sparse() {
    
    for (int i = 1 ; i <= n ; ++i)
        sparse[0][i] = jump[i];

    for (int log = 1 ; (1 << log) <= n ; ++log)
        for (int i = 1 ; i <= n ; ++i)
            sparse[log][i] = sparse[log-1][sparse[log-1][i]];

}

int lifting(int l, int r) {

    int ans = 0;
    for (int log = maxlog-1 ; log >= 0 ; --log) {

        if (sparse[log][l] == 0) continue;
        if (sparse[log][l] <= r+1) {

            ans += (1 << log);
            l = sparse[log][l];

        }

    }

    return ans;

}

unordered_map < long long, int > um;
void solve() {

    fill(jump, jump+n+1, n+2);

    long long sum = 0;
    for (int i = 1 ; i <= n+1 ; ++i) {

        jump[um[sum]] = i;
        um[sum] = i;
        sum += a[i];

    }


    for (int i = n-1 ; i >= 1 ; --i) jump[i] = min(jump[i], jump[i+1]);

    build_sparse();

    int l, r;
    cin >> q;

    for (int i = 1 ; i <= q ; ++i) {

        cin >> l >> r;
        cout << lifting(l, r) << '\n';

    }


}

void fast_io() {

    ios_base :: sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cerr.tie(nullptr);

}

void read() {

    cin >> n;
    for (int i = 1 ; i <= n ; ++i)
        cin >> a[i];

}

int main () {

    fast_io();
    read();
    solve();

    return 0;
    
}

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