제출 #1225661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225661		Ghulam_Junaid	Sum Zero (RMI20_sumzero)	C++20	61 / 100	338 ms	47072 KiB

sumzero

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

typedef long long ll;

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    map<ll, int> last;
    last[0] = 0;
    for (int i = 1; i <= n + 2; i ++)
        par[i][0] = n + 2;
    for (int i = 1; i <= n; i ++){
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
        if (last.find(p[i]) != last.end())
            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);
            }
        }
        cout << ans << '\n';
    }
}

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