Submission #549275

#	Time	Username	Problem	Language	Result	Execution time	Memory
549275		kevinxiehk	Sum Zero (RMI20_sumzero)	C++17	61 / 100	361 ms	24980 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][2];
int qus[400005][3];
int nxt[400005];
long long ps[400005];
signed main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    map<long long, int> la;
    ps[0] = 0;
    for(int i = 1; i <= n; i++) {
        cin >> ps[i];
        ps[i] = ps[i - 1] + ps[i];
        nxt[i] = n + 1;
        if(la[ps[i]] != 0 || ps[i] == 0) {
            nxt[la[ps[i]] + 1] = min(nxt[la[ps[i]] + 1], i);
        }
        la[ps[i]] = i;
    }
    for(int i = n - 1; i >= 1; i--) {
        nxt[i] = min(nxt[i], nxt[i + 1]);
    }
    // for(int i = 1; i <= n; i++) {
    //     cout << next[i] << ' ';
    // }cout << '\n'; //return 0;
    
    nxt[n + 1] = n + 1;
    nxt[n + 2] = n + 1;
    for(int i = 1; i <= n + 2; i++) {
        sps[i][0] = nxt[i];
    }
    
    int q;
    cin >> q;
    for(int i = 0; i < q; i++) {
        cin >> qus[i][0] >> qus[i][1];
        qus[i][2] = 0;
    }
    for(int k = 19; k >= 0; k--) {
        for(int i = 1; i <= n + 2; i++) {
            sps[i][0] = nxt[i];
        }
        for(int j = 1; j <= k; j++) {
            for(int i = 1; i <= n + 2; i++) {
                sps[i][j & 1] = sps[sps[i][(j & 1) ^ 1] + 1][(j & 1) ^ 1];
                if(sps[i][j & 1] > n) sps[i][j & 1] = n + 1;
                // cout << sps[i][j] << ' ';
            }
            // cout << '\n';
        }//return 0;
        for(int i = 0; i < q; i++) {
            if(sps[qus[i][0]][k & 1] <= qus[i][1]) {
                qus[i][0] = sps[qus[i][0]][k & 1] + 1;
                qus[i][2] += (1 << k);
            }
        }
    }
    // 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';
    // }
    for(int i = 0; i < q; i++) cout << qus[i][2] << '\n';

    return 0;
}

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