Submission #549273

#	Time	Username	Problem	Language	Result	Execution time	Memory
549273		kevinxiehk	Sum Zero (RMI20_sumzero)	C++17	61 / 100	608 ms	56284 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 1e9
#define ick cout<<"ickbmi32.9\n"
using namespace std;
int sps[400005][20];
signed main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    int arr[n + 5];
    long long ps[n + 5];
    int next[n + 5];
    map<long long, 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;
    
    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: 39 / 39
• Subtask 3: 0 / 39