Submission #1262916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262916		trinhvtuan	Sum Zero (RMI20_sumzero)	C++20	61 / 100	257 ms	46084 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 500000 + 5;
const int LOG = 20; // enough for n <= 4e5

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

    int n;
    if(!(cin >> n)) return 0;
    vector<ll> a(n+1);
    for(int i=1;i<=n;i++) cin >> a[i];

    // prepare prefix sums nodes (value, position)
    // include position 0 (prefix sum = 0)
    vector<pair<ll,int>> pref; pref.reserve(n+1);
    ll cur = 0;
    pref.push_back({0, 0}); // position 0
    for(int i=1;i<=n;i++){
        cur += a[i];
        pref.push_back({cur, i});
    }
    // sort by value then by position
    sort(pref.begin(), pref.end(), [](const pair<ll,int>& p1, const pair<ll,int>& p2){
        if(p1.first != p2.first) return p1.first < p2.first;
        return p1.second < p2.second;
    });

    // lf[pos] = previous position with same prefix sum (or -1)
    vector<int> lf(n+1, -1);
    for(size_t i=1;i<pref.size();++i){
        if(pref[i].first == pref[i-1].first){
            int curpos = pref[i].second;
            int prevpos = pref[i-1].second;
            // curpos can be 0..n, but we only store lf for positions 0..n.
            if(curpos >= 0 && curpos <= n) lf[curpos] = prevpos;
        }
    }

    // accumulate so lf[i] = max(lf[i], lf[i-1]) to get rightmost previous occurrence <= i
    for(int i=1;i<=n;i++){
        lf[i] = max(lf[i], lf[i-1]);
    }

    // build binary lifting table st[i][k]: jump 2^k steps of "previous equal" from i
    // use -1 as sentinel (no jump)
    vector<array<int, LOG+1>> st(n+1);
    for(int i=0;i<=n;i++){
        for(int j=0;j<=LOG;j++) st[i][j] = -1;
    }
    for(int i=1;i<=n;i++){
        st[i][0] = lf[i]; // could be -1 or 0..n
    }
    for(int k=1;k<=LOG;k++){
        for(int i=1;i<=n;i++){
            int mid = st[i][k-1];
            if(mid != -1) st[i][k] = st[mid][k-1];
            else st[i][k] = -1;
        }
    }

    int Q; cin >> Q;
    while(Q--){
        int L,R; cin >> L >> R;
        int u = R;
        int ans = 0;
        for(int k=LOG;k>=0;k--){
            if(st[u][k] != -1 && st[u][k] + 1 >= L){
                ans += (1<<k);
                u = st[u][k];
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

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