Submission #494535

#	Time	Username	Problem	Language	Result	Execution time	Memory
494535		TITANOBOXER	Sum Zero (RMI20_sumzero)	C++17	61 / 100	461 ms	41548 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'

const int N = 4e5 + 7;
const int LOG = 17;

int a[N];
int best_id[N][LOG];

int query(int l,int r) {
    int ans = 0;
    for(int log = LOG - 1;log >= 0; --log) {
        if(best_id[l][log] && best_id[l][log] - 1 <= r) {
            ans += (1 << log);
            l = best_id[l][log];
        }
    }
    return ans;
}

signed main() {
    fast;
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    unordered_map<int64_t,int> lst_pos;
    lst_pos[0] = n + 1;
    int64_t cur = 0;
    for(int i = n,prv = 2e9;i >= 1; --i) {
        cur += a[i];
        if(lst_pos[cur]) {
            prv = min(prv,lst_pos[cur]);
        }
        best_id[i][0] = prv;
        lst_pos[cur] = i;
    }
    for(int log = 1; log < LOG; ++log) {
        for(int i = 1; i + (1 << log) - 1 <= n; ++i) {
            if(best_id[i][log - 1] > n) best_id[i][log] = 2e9;
            else best_id[i][log] = best_id[best_id[i][log - 1]][log - 1];
        }
    }
    int q;
    cin >> q;
    while(q--) {
        int l,r;
        cin >> l >> r;
        cout << query(l,r) << endl;
    }
    return 0;
}

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