제출 #549274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
549274		kevinxiehk	Sum Zero (RMI20_sumzero)	C++17	61 / 100	369 ms	26536 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];
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];
    }
    
    int q;
    cin >> q;
    int qus[q + 5][3];
    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] = next[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