Overview

For each plan, this problem asks you to compute the sum of temperatures over the interval \([L_i, R_i]\) and determine whether it meets or exceeds the threshold \(K_i\).
The key idea is to use a prefix sum to efficiently compute interval sums multiple times.

Analysis

In this problem, for each query we need to compute

\(A_{L_i} + A_{L_i+1} + \cdots + A_{R_i}\)

and compare it with \(K_i\).

Naive Approach

For example, if we consider summing from \(L_i\) to \(R_i\) sequentially for each plan, a single query takes up to \(O(N)\) time.
Doing this \(M\) times results in a worst case of \(O(NM)\).

The constraints for this problem are:

• \(N \le 2 \times 10^5\)
• \(M \le 10^5\)

So \(O(NM)\) can be as large as about \(2 \times 10^{10}\), which is far too slow.

Key Insight

If we need to compute interval sums many times, precomputing a prefix sum array makes this much faster.

Define the prefix sum prefix as:

• prefix[0] = 0
• prefix[i] = A_1 + A_2 + \cdots + A_i

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

\(A_L + A_{L+1} + \cdots + A_R = \text{prefix}[R] - \text{prefix}[L-1]\)

Concrete Example

For example, given

\(A = [3, -2, 5, 1, 4]\)

the prefix sums are:

• prefix[0] = 0
• prefix[1] = 3
• prefix[2] = 1
• prefix[3] = 6
• prefix[4] = 7
• prefix[5] = 11

The sum over the interval \([2,4]\) is

\(A_2 + A_3 + A_4 = -2 + 5 + 1 = 4\)

Using the prefix sum, this can be computed as:

\(\text{prefix}[4] - \text{prefix}[1] = 7 - 3 = 4\)

With this approach, each query can be processed in \(O(1)\).

Algorithm

1. Read the array \(A\).
2. Build a prefix sum array prefix of length \(N+1\).
   • prefix[0] = 0
   • prefix[i+1] = prefix[i] + A[i]
3. For each query \((L, R, K)\), compute the interval sum $\( s = \text{prefix}[R] - \text{prefix}[L-1] \)$
4. If \(s \ge K\), output Dangerous; otherwise, output Safe.

Complexity

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

Implementation Notes

• Since the query values \(L, R\) are 1-indexed, it is convenient to prepare prefix[0] in the prefix sum array accordingly.

• The interval sum is computed as prefix[R] - prefix[L - 1].

• Even if \(A_j\) contains negative values, the prefix sum works correctly as-is.

• Since the number of queries can be large, in Python it is advisable to read all input at once using sys.stdin.buffer.read() for fast input, and to collect output in a list and print it all at once with "\n".join(...) for stability.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)

    A = [next(it) for _ in range(N)]

    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]

    out = []
    for _ in range(M):
        L = next(it)
        R = next(it)
        K = next(it)
        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.4-high.