Submission #1263305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263305		rshohruh	Sum Zero (RMI20_sumzero)	C++20	0 / 100	3 ms	832 KiB

sumzero

// rshohruh

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    vector<int> up0(n+1, -1); // only direct jumps
    map<ll,int> mp;
    mp[0] = 0;
    ll pref = 0;
    int id = -1;
    for(int i = 1; i <= n; i++){
        pref += a[i];
        if(mp.count(pref)) id = max(id, mp[pref]);
        up0[i] = id;
        mp[pref] = i;
    }

    // lazy higher jumps
    const int LOG = 20;
    vector<vector<int>> up(LOG, vector<int>(n+1, -2));
    for(int i = 0; i <= n; i++) up[0][i] = up0[i];

    auto getUp = [&](auto self, int j, int i) -> int {
        if(i == -1) return -1;
        if(up[j][i] != -2) return up[j][i]; // cached
        int half = self(self, j-1, i);
        if(half == -1) return up[j][i] = -1;
        return up[j][i] = self(self, j-1, half);
    };

    int q; cin >> q;
    while(q--){
        int l, r; cin >> l >> r;
        int ans = 0;
        for(int j = LOG-1; j >= 0; j--){
            int nxt = getUp(getUp, j, r);
            if(nxt >= l){
                ans += (1<<j);
                r = nxt;
            }
        }
        cout << ans << '\n';
    }
}

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