제출 #1279722

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279722		rayan_bd	Sum Zero (RMI20_sumzero)	C++20	22 / 100	155 ms	25980 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
const int mxN = 4e5 + 100;
const int mxB = 29;

#define int long long

int a[mxN], dp[mxN][mxB];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    int n, l, r, q;
    cin >> n;

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

    cin >> q;

    unordered_map<int, int> mp;

    mp[0] = n + 1;

    // 0 1 2 -3 100
    //

    dp[n + 1][0] = n + 5;

    for(int i = n, sum = 0; i >= 1; --i){
        sum += a[i];
        if(mp.count(sum)){
            dp[i][0] = min(dp[i + 1][0], mp[sum]);
        }else{
            dp[i][0] = dp[i + 1][0];
        }
        mp[sum] = i;
    }

    for (int j = 1; j < mxB; j++) {
        for (int i = 1; i <= n; i++) {
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }


    while (q--) {
        cin >> l >> r;
        int ans = 0;
        for (int j = mxB - 1; j >= 0; j--) {
            if (dp[l][j] <= (r + 1) && dp[l][j] > l) {
                l = dp[l][j];
                ans += (1 << j);
            }
        }
        cout << ans << "\n";
    }

    return 0;
}

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