Overview

This is a problem where you need to compute range sums of an array and compare them against thresholds. By using a prefix sum, each query can be answered in \(O(1)\).

Analysis

Naive Approach and Its Issues

If we naively sum from \(A_{L_i}\) to \(A_{R_i}\) for each plan, a single query takes up to \(O(N)\). Since there are \(M\) plans, the overall complexity becomes \(O(NM)\). When \(N = 2 \times 10^5\) and \(M = 10^5\), this requires up to \(2 \times 10^{10}\) operations, which will not fit within the time limit (TLE).

Key Insight

Range sum computation can be done in \(O(1)\) for any interval if we precompute a prefix sum array.

Define the prefix sum array \(S\) as follows:

\[S_0 = 0, \quad S_i = A_1 + A_2 + \cdots + A_i \quad (1 \leq i \leq N)\]

Then, the sum of the interval \([L, R]\) can be computed as:

\[A_L + A_{L+1} + \cdots + A_R = S_R - S_{L-1}\]

Concrete Example

For example, when \(A = [3, -1, 4, 1, 5]\), the prefix sums are:

\(i\)	0	1	2	3	4	5
\(S_i\)	0	3	2	6	7	12

The range sum for \(L=2, R=4\) is \(S_4 - S_1 = 7 - 3 = 4\), which indeed matches \(A_2 + A_3 + A_4 = -1 + 4 + 1 = 4\).

Algorithm

1. Preprocessing: Build the prefix sum array \(S\) from array \(A\) in \(O(N)\).
2. Answering each query: For the \(i\)-th plan, compute the range sum \(s = S_{R_i} - S_{L_i - 1}\) in \(O(1)\).
3. Judgment: If \(s \geq K_i\), output Dangerous; otherwise, output Safe.

Complexity

• Time complexity: \(O(N + M)\) (building the prefix sum takes \(O(N)\), and processing each query takes \(O(1)\) × \(M\) times)
• Space complexity: \(O(N)\) (for the prefix sum array)

Implementation Notes

• Handling 1-indexed input: Since the problem numbers positions starting from \(1\), we create the prefix sum array with length \(N+1\) where prefix[0] = 0, and obtain the range sum using prefix[R] - prefix[L-1].

• Fast I/O: In Python, we speed up input using sys.stdin.readline, and reduce I/O overhead by accumulating output into a string list and printing it all at once with '\n'.join(out) at the end.

• No overflow concerns: Since Python has no limit on integer size, we can compute without worrying about overflow even when \(A_j\) values are negative or \(K_i\) is a large negative value.

  Source Code

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    
    # prefix sum
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]
    
    out = []
    for _ in range(M):
        L, R, K = map(int, input().split())
        s = prefix[R] - prefix[L - 1]
        if s >= K:
            out.append("Dangerous")
        else:
            out.append("Safe")
    
    print('\n'.join(out))

main()

---

This editorial was generated by claude4.6opus-thinking.