Overview

Given the temperatures at \(N\) locations, the problem asks us to determine, for \(M\) queries, whether the sum of temperatures (heat load) over a specified interval \([L_i, R_i]\) is at least the threshold \(K_i\).

Analysis

The most straightforward approach is to loop from \(L_i\) to \(R_i\) for each query and sum up the temperatures. However, this method requires up to \(N\) additions per query. Since there are \(M\) queries, the worst-case time complexity is \(O(N \times M)\).

Given the constraints of this problem, \(N \leq 2 \times 10^5, M \leq 10^5\), the worst case would require approximately \(2 \times 10^{10}\) operations, which exceeds the time limit (generally, about \(10^8\) operations can be processed per second).

Therefore, we use a technique called prefix sums, which allows us to compute the sum of any interval in \(O(1)\) (constant time).

Algorithm

Using Prefix Sums

First, we precompute the cumulative sum of temperatures from the first location to each location. We call this the prefix sum array \(S\), defined as follows: - \(S[0] = 0\) - \(S[i] = A_1 + A_2 + \cdots + A_i\) (\(1 \leq i \leq N\))

Here, \(S[i]\) can be computed sequentially using the formula \(S[i] = S[i-1] + A_i\).

Once this array \(S\) is constructed, the sum over any interval \([L, R]\) can be obtained with just the following calculation: $\(\sum_{j=L}^{R} A_j = S[R] - S[L-1]\)$

Concrete Example

For example, if the temperatures are \(A = [3, 1, 4, 1, 5]\), the prefix sums are \(S = [0, 3, 4, 8, 9, 14]\). If we want to find the sum from the 2nd to the 4th element (\(1+4+1=6\)): \(S[4] - S[2-1] = S[4] - S[1] = 9 - 3 = 6\) We can confirm that the calculation is correct.

Complexity

• Time Complexity: \(O(N + M)\)
  • Building the prefix sums takes \(O(N)\), and processing each query takes \(O(1)\), so the overall complexity is \(O(N + M)\). This is sufficiently fast under the given constraints.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the prefix sum array of length \(N+1\).

Implementation Notes

• Fast I/O: In Python, repeatedly calling input() and print() many times can make I/O a bottleneck. By reading all input at once with sys.stdin.read().split() and writing all output at once with sys.stdout.write(), execution time can be reduced.

• Index handling: In the problem statement, locations are given as 1-based (starting from 1). By creating the prefix sum array \(S\) with size \(N+1\) and setting \(S[0]=0\), we can intuitively write \(S[R] - S[L-1]\) for 1-based queries \(L, R\).

  Source Code

import sys

def solve():
    # 入力をすべて読み込み、空白で分割してリストにする（高速化のため）
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用して各要素を順番に取得する
    it = iter(input_data)
    
    # 地点の数 N と 計画の数 M を取得
    N = int(next(it))
    M = int(next(it))
    
    # 累積和を格納する配列 S を用意する
    # S[i] は 1 番目から i 番目までの地点の気温の合計を保持する
    S = [0] * (N + 1)
    current_total = 0
    for i in range(1, N + 1):
        current_total += int(next(it))
        S[i] = current_total
        
    # 各計画（クエリ）を処理する
    results = []
    for _ in range(M):
        L = int(next(it))
        R = int(next(it))
        K = int(next(it))
        
        # 区間 [L, R] の気温の合計は累積和の差 S[R] - S[L-1] で求められる
        heat_load = S[R] - S[L-1]
        
        # 熱負荷が閾値 K 以上であれば Dangerous、そうでなければ Safe
        if heat_load >= K:
            results.append("Dangerous")
        else:
            results.append("Safe")
            
    # 全ての結果を改行で連結して一気に出力する（高速化のため）
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-thinking.