Submission #494603

#	Time	Username	Problem	Language	Result	Execution time	Memory
494603		TITANOBOXER	Sum Zero (RMI20_sumzero)	C++17	0 / 100	5 ms	588 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 = 11;

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

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

signed main() {
    fast;
    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 <= n; ++i) {
            if(!best_id[i][log - 1] || best_id[i][log - 1] > n + 2) continue;
            if(!best_id[best_id[i][log - 1]][log - 1] || best_id[best_id[i][log - 1]][log - 1] > n + 2) continue;
            if(!best_id[best_id[best_id[i][log - 1]][log - 1]][log - 1] || best_id[best_id[best_id[i][log - 1]][log - 1]][log - 1] > n + 2) continue;
            best_id[i][log] = best_id[best_id[best_id[best_id[i][log - 1]][log - 1]][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: 0 / 22
• Subtask 2: 0 / 39
• Subtask 3: 0 / 39