Submission #1242016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242016		hssaan_arif	Sum Zero (RMI20_sumzero)	C++20	0 / 100	1 ms	576 KiB

sumzero

#include<bits/stdc++.h>
using namespace std;

#define endl "\n"
#define pb push_back
#define int long long

const int N = 4e5 + 5, M = 1e9 + 7 , LG = 26;

int n , a[N] , pr[N] , prv[N] ,last[N] , Q ,L,R , sp[N][LG];

void solve(){
    cin >> n;
    for (int i = 1 ; i <= n ; i++){
        cin >> a[i];
    }
    for (int i = 1 ; i <= n ; i++){
        pr[i] = pr[i-1] + a[i];
        int k = last[pr[i]];
        last[pr[i]] = i;
        prv[i] = max(prv[i-1],k);
        sp[i][0] = prv[i];
        for (int j = 1 ; j < LG ; j++){
            sp[i][j] = sp[sp[i][j-1]][j-1];
        }
    }
    cin >> Q;
    while(Q--){
        cin >> L >> R;
        int ans = 0;
        for (int i = LG - 1 ; i >= 0 ; i--){
            if (sp[R][i] >= L){
                R = sp[R][i];
                ans += (1 << i);
            }
        }
        
        if (sp[R][0] >= L - 1){
            ans++;
        }
        cout << ans << endl;
    }
    // cout << sp[3][0] << endl;
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ts = 1;
    // cin >> ts;
    while(ts--){
        solve();
    }
}

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