제출 #1273756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273756		nguyenbaoanh	Sum Zero (RMI20_sumzero)	C++20	0 / 100	3 ms	1336 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if(!(cin >> n)) return 0;
    vector<ll> a(n+1,0), pre(n+1,0);
    for(int i=1;i<=n;i++){
        ll x; cin >> x;
        a[i] = x;
        pre[i] = pre[i-1] + a[i];
    }

    // positions of each prefix sum
    unordered_map<ll, vector<int>> pos;
    pos.reserve(n*2);
    for(int i=0;i<=n;i++){
        pos[pre[i]].push_back(i);
    }

    // build next: next[i] = smallest j>i with pre[j]==pre[i], else n+1
    vector<int> nxt(n+1, n+1);
    for(auto &kv : pos){
        auto &vec = kv.second;
        // vec already in increasing order since we pushed i from 0..n
        for(size_t k=0;k+1<vec.size();++k){
            nxt[ vec[k] ] = vec[k+1];
        }
        // last stays n+1
    }

    // binary lifting on indices 0..n, use sentinel n+1
    int LOG = 20; // 2^20 > 1e6, enough for n up to ~1e6
    vector<vector<int>> up(LOG, vector<int>(n+2, n+1));
    vector<vector<int>> cnt(LOG, vector<int>(n+2, 0));

    for(int i=0;i<=n;i++){
        if(nxt[i] <= n){
            up[0][i] = nxt[i];
            cnt[0][i] = 1;
        } else {
            up[0][i] = n+1;
            cnt[0][i] = 0;
        }
    }
    up[0][n+1] = n+1; cnt[0][n+1] = 0;

    for(int k=1;k<LOG;k++){
        for(int i=0;i<=n+1;i++){
            up[k][i] = up[k-1][ up[k-1][i] ];
            cnt[k][i] = cnt[k-1][i] + cnt[k-1][ up[k-1][i] ];
        }
    }

    int q; cin >> q;
    while(q--){
        int L,R; cin >> L >> R;
        int posi = L-1; // work on prefix indices
        int ans = 0;
        for(int k=LOG-1;k>=0;k--){
            if(up[k][posi] <= R){
                ans += cnt[k][posi];
                posi = up[k][posi];
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

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