제출 #1273732

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

sumzero

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
const int N=2e5;
int n, q;
ii up[N+5][20];
ll a[N+5], pre[N+5];
unordered_map<ll, queue<int>> mp; // lưu nhiều vị trí cho cùng 1 prefix

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        pre[i] = pre[i-1] + a[i];
    }

    // Gom tất cả chỉ số theo prefix sum
    for(int i=0; i<=n; i++) mp[pre[i]].push(i);

    // Xây next-step cho binary lifting
    for(int i=0; i<=n; i++) {
        // bỏ chính i ra khỏi hàng đợi (để "kế tiếp" thực sự là sau nó)
        mp[pre[i]].pop();
        if(!mp[pre[i]].empty()) {
            int nxt = mp[pre[i]].front();
            up[i+1][0] = {nxt+1, 1};  // vì l trong query là 1-based → dịch +1
        } else {
            up[i+1][0] = {i+2, 0};
        }
    }

    // gán thêm cho n+1, n+2 để an toàn
    up[n+1][0] = {n+2, 0};
    up[n+2][0] = {n+2, 0};

    // Build binary lifting
    for(int j=1; j<20; j++) {
        for(int i=1; i<=n+2; i++) {
            ii t = up[i][j-1];
            up[i][j].first  = up[t.first][j-1].first;
            up[i][j].second = t.second + up[t.first][j-1].second;
        }
    }

    cin >> q;
    while(q--) {
        int l, r; cin >> l >> r;
        int res = 0;
        for(int j=19; j>=0; j--) {
            while(up[l][j].first-1 <= r && l <= r) {
                res += up[l][j].second;
                l = up[l][j].first;
            }
        }
        cout << res << '\n';
    }
}

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