제출 #549272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
549272		kevinxiehk	Sum Zero (RMI20_sumzero)	C++17	22 / 100	132 ms	26648 KiB

sumzero

#include <bits/stdc++.h>
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
#define int long long
#define inf 1e18
#define ick cout<<"ickbmi32.9\n"
using namespace std;

signed main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    int arr[n + 5];
    int ps[n + 5];
    int next[n + 5];
    map<int, int> la;
    ps[0] = 0;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        ps[i] = ps[i - 1] + arr[i];
        next[i] = n + 1;
        if(la[ps[i]] != 0 || ps[i] == 0) {
            next[la[ps[i]] + 1] = min(next[la[ps[i]] + 1], i);
        }
        la[ps[i]] = i;
    }
    for(int i = n - 1; i >= 1; i--) {
        next[i] = min(next[i], next[i + 1]);
    }
    // for(int i = 1; i <= n; i++) {
    //     cout << next[i] << ' ';
    // }cout << '\n'; //return 0;
    int sps[n + 5][25];
    next[n + 1] = n + 1;
    next[n + 2] = n + 1;
    for(int i = 1; i <= n + 2; i++) {
        sps[i][0] = next[i];
    }
    for(int j = 1; j < 20; j++) {
        for(int i = 1; i <= n + 2; i++) {
            sps[i][j] = sps[sps[i][j - 1] + 1][j - 1];
            if(sps[i][j] > n) sps[i][j] = n + 1;
            // cout << sps[i][j] << ' ';
        }
        // cout << '\n';
    }//return 0;
    int q;
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        int ans = 0;
        for(int i = 19; i >= 0; i--) {
            if(sps[l][i] <= r) {
                ans += (1 << i);
                l = sps[l][i] + 1;
            }
        }
        cout << ans << '\n';
    }

    return 0;
}

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