Submission #1225680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225680		Ghulam_Junaid	Sum Zero (RMI20_sumzero)	C++20	61 / 100	566 ms	28796 KiB

sumzero

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

typedef long long ll;

const int N = 4e5 + 5, LG = 10;
int n, q, last[N], par[N][LG];
ll p[N];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    memset(last, -1, sizeof last);

    cin >> n;
    for (int i = 1; i <= n + 2; i ++)
        par[i][0] = n + 2;
    
    vector<pair<ll, int>> vec(n + 1);
    vec[0] = {p[0], 0};
    for (int i = 1; i <= n; i ++){
        cin >> p[i];
        p[i] += p[i - 1];
        vec[i] = {p[i], i};
    }
    sort(vec.begin(), vec.end());

    for (int i = 0; i <= n; i ++){
        int r = i;
        while (r <= n and vec[r].first == vec[i].first)
            r++;
        for (int j = i; j < r; j ++)
            p[vec[j].second] = i;
        i = r - 1;
    }

    last[p[0]] = 0;
    for (int i = 1; i <= n; i ++){
        if (last[p[i]] != -1) par[last[p[i]] + 1][0] = i + 1;
        last[p[i]] = i;
    }

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

    for (int j = 1; j < LG; j ++)
        for (int i = 1; i <= n + 2; i ++)
            par[i][j] = par[par[i][j - 1]][j - 1];

    cin >> q;
    while (q--){
        int l, r;
        cin >> l >> r;

        int cur = l, ans = 0;
        for (int i = LG - 1; i >= 0; i --){
            if (par[cur][i] <= r + 1){
                cur = par[cur][i];
                ans += (1 << i);
                i++;
            }
        }
        cout << ans << '\n';
    }
}

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