Submission #1316234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316234		sefat	Sum Zero (RMI20_sumzero)	C++20	61 / 100	362 ms	47080 KiB

sumzero

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

// Define long long for prefix sums as values can exceed 2^31
typedef long long ll;

// Constraints: N <= 400,000. 
// We use 400,005 for safety.
const int MAXN = 400005;
const int LOGN = 20; // 2^19 > 400,000, so 20 is plenty safe.

// Global arrays to prevent stack overflow
int jump[LOGN][MAXN];
ll pr[MAXN];
int n, q;

void solve() {
    if (!(cin >> n)) return;

    // Reading input and building prefix sums
    // pr[i] stores the sum of c[1]...c[i]
    pr[0] = 0;
    for(int i = 1; i <= n; ++i) {
        int val;
        cin >> val;
        pr[i] = pr[i-1] + val;
    }

    cin >> q;

    // 'mp' stores the LAST seen position of a prefix sum while iterating backwards.
    // Effectively, for current index 'i', it tells us the nearest 'j' >= i such that pr[j] == val.
    map<ll, int> mp;
    
    // Initialize the 'infinity' limit
    // If a subarray ends at 'n', the next one would start at 'n+1'.
    // So 'n+2' is a safe "infinity" / "no solution" marker.
    int INF = n + 2;
    
    // Initialize base cases for binary lifting beyond valid range
    for(int j = 0; j < LOGN; j++) {
        jump[j][n + 1] = INF;
        jump[j][n + 2] = INF;
    }

    // We keep track of the earliest ending position of a valid zero-sum subarray
    // found so far to the right.
    int min_end = INF;

    // Fill mp with the final prefix sum to handle cases where a subarray ends at N
    mp[pr[n]] = n;

    // Iterate backwards to build the first level of the jump table (jump[0])
    // jump[0][i] = (end index of the nearest zero-sum subarray starting >= i) + 1
    for(int i = n; i >= 1; --i) {
        
        // Check if there is a prefix sum P[j] == P[i-1] to the right
        // If yes, a zero-sum subarray exists from i to j.
        if (mp.count(pr[i-1])) {
            int segment_end = mp[pr[i-1]];
            min_end = min(min_end, segment_end);
        }

        // jump[0][i] points to the start of the NEXT disjoint subarray.
        // If the best segment we found ends at 'min_end', the next one starts at 'min_end + 1'.
        jump[0][i] = min_end + 1;

        // Update map: current 'i' is now the leftmost occurrence of pr[i] seen so far
        // (but actually we need to store pr[i] for the future iterations i-1, i-2...)
        // effectively, mp[val] always stores the smallest index k >= current_i with pr[k] == val
        mp[pr[i-1]] = i - 1; // Correct logic is to store the index for P[i-1] check? 
                             // No, wait. For the NEXT iteration (i-1), we want to find P[(i-1)-1].
                             // The current iteration establishes P[i] is at index i.
        // Actually, the simple logic is: 
        // We just processed index i. We want to make sure P[i-1] is available for future lookups of P[something] == P[i-1].
        // But actually, we only need to update the map with the current prefix sum `pr[i-1]` 
        // is NOT relevant for the right side matching. We need to add `pr[i-1]` as a potential END point for a subarray starting to the left?
        // No.
        
        // Let's re-verify map update logic:
        // A subarray starting at 'start' ends at 'end' if pr[end] == pr[start-1].
        // When we are at 'i', we are the 'start'. We look for 'end' > 'i' such that pr[end] == pr[i-1].
        // So we need the map to store positions of pr values to the RIGHT.
        // So at step 'i', we should add `pr[i-1]` to the map? No, `pr[i-1]` is the value BEFORE index i. 
        // We are looking for a match to the right. The values to the right are `pr[i], pr[i+1]...`.
        // So we should have added `pr[i]` to the map in the PREVIOUS iteration (i+1).
        
        // Correct Loop Structure:
        // 1. Calculate best match for current 'i'. Match is found if `pr[i-1]` exists in map.
        // 2. Update `min_end`.
        // 3. Update map with `pr[i-1]`? No! `pr[i-1]` is a potential END point for a subarray starting at `i-something`.
        //    But here we are moving left.
        //    Ah, the map must store indices `k` where `pr[k]` exists.
        //    At start of loop `i`, map contains indices `k > i`.
        //    We check `pr[i-1]`.
        //    Before going to `i-1`, we must add index `i-1` to the map? 
        //    No, index `i-1` is an END point for a subarray starting at `Left`.
        //    So yes, we add `pr[i-1]` at index `i-1`.
        
        mp[pr[i-1]] = i - 1; 
    }

    // Binary Lifting Construction
    // jump[j][i] is the starting position of the subarray after 2^j segments have been picked
    for(int j = 1; j < LOGN; ++j) {
        for(int i = 1; i <= n + 1; ++i) {
            int mid = jump[j-1][i];
            if(mid > n + 1) jump[j][i] = INF;
            else jump[j][i] = jump[j-1][mid];
        }
    }

    // Process Queries
    while(q--) {
        int l, r;
        cin >> l >> r;
        
        int ans = 0;
        int curr = l;
        
        for(int j = LOGN - 1; j >= 0; --j) {
            // We want to jump 2^j steps. 
            // jump[j][curr] gives the START position of the (2^j + 1)-th segment.
            // If that start position is valid (meaning the 2^j-th segment ended <= r), we take it?
            // Wait, the definition: jump[j][curr] is the start of the next segment 
            // AFTER consuming 2^j segments starting from curr.
            // So if jump[j][curr] - 1 <= r, it means all 2^j segments fit completely within [l, r].
            
            if(jump[j][curr] <= r + 1) { 
                // Why r+1?
                // jump[j][curr] is the start of the (2^j + 1)-th segment.
                // The previous segment ended at jump[j][curr] - 1.
                // We need that end <= r.
                // So jump[j][curr] - 1 <= r  =>  jump[j][curr] <= r + 1.
                
                ans += (1 << j);
                curr = jump[j][curr];
            }
        }
        cout << ans << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

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