Overview

For each plan, this problem asks us to determine whether the “sum of temperatures over the interval \([L, R]\)” is at least the threshold \(K\).
To efficiently handle a large number of range sum queries, we use a prefix sum.

Analysis

The essence of this problem is to quickly compute, for each query, [ AL + A{L+1} + \cdots + A_R ]

Naive Approach

If we sum from \(L\) to \(R\) for each query, it takes \(O(N)\) per query in the worst case.
Since the number of queries is at most \(M=10^5\), the total worst case is \(O(NM)\) (approximately \(2\times 10^{10}\)), which will not finish in time (TLE).

Key Insight

Range sums can be computed instantly using prefix sums.

Define the prefix sum array prefix as [ \text{prefix}[i] = A_1 + A_2 + \cdots + A_i ] (with prefix[0]=0). Then, [ A_L + \cdots + A_R = \text{prefix}[R] - \text{prefix}[L-1] ]

This allows each query to be answered in \(O(1)\).

For example, when \(A=[3,-2,5,1]\),
prefix=[0,3,1,6,7].
The sum over the interval \([2,4]\) is [ \text{prefix}[4]-\text{prefix}[1]=7-3=4 ]

Algorithm

1. Read the input.
2. Create a prefix sum array prefix of length \(N+1\) (with prefix[0]=0).
3. For i=1..N, compute prefix[i] = prefix[i-1] + A[i] (adjust for 0-indexed arrays in the implementation).
4. For each query \((L, R, K)\):
   • Compute s = prefix[R] - prefix[L-1]
   • If s >= K, add Dangerous to the output list; otherwise add Safe
5. Output everything at the end.

Complexity

• Time complexity: \(O(N + M)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Since \(L, R\) are given as 1-indexed, it is safe to create prefix with length N+1 so that the formula prefix[R] - prefix[L-1] can be used directly.

• The prefix sum works correctly even when values include negative numbers.

• In Python, for optimization, use sys.stdin.readline for input, and collect outputs in a list and print them all at once with "\n".join(...).

  Source Code

import sys

def main():
    input = sys.stdin.readline

    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    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]
        out.append("Dangerous" if s >= K else "Safe")

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.