B - 気温チェック 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 333 点

問題文

高橋君は、一直線に並んだ N 個の地点を通るハイキングコースの計画を立てています。

j 番目の地点の気温は A_j です。

L 番目の地点から R 番目の地点まで歩くとき、その区間で受ける 熱負荷 を気温の合計 A_L + A_{L+1} + \cdots + A_R で定めます。熱負荷が閾値 K 以上であれば「危険」、K 未満であれば「安全」と判定します。

M 個の計画が与えられます。i 番目の計画では、L_i 番目の地点から R_i 番目の地点まで歩きます。この計画に対する閾値は K_i です。各計画について「危険」か「安全」かを判定してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 10^5
  • -10^4 \leq A_j \leq 10^4 （1 \leq j \leq N）
  • 1 \leq L_i \leq R_i \leq N （1 \leq i \leq M）
  • -2 \times 10^9 \leq K_i \leq 2 \times 10^9 （1 \leq i \leq M）
  • 入力はすべて整数である

入力

N M
A_1 A_2 \cdots A_N
L_1 R_1 K_1
L_2 R_2 K_2
\vdots
L_M R_M K_M
  • 1 行目には、地点の数 N と計画の数 M が、スペース区切りで与えられる。
  • 2 行目には、各地点の気温 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 2 + i 行目（1 \leq i \leq M）には、i 番目の計画を表す区間の始点 L_i、終点 R_i、閾値 K_i が、スペース区切りで与えられる。

出力

M 行出力せよ。

i 行目には、i 番目の計画について、A_{L_i} + A_{L_i+1} + \cdots + A_{R_i} \geq K_i ならば Dangerous を、そうでなければ Safe を出力せよ。

入力例 1

5 4
3 1 4 1 5
1 3 8
2 4 7
4 5 6
5 5 10

出力例 1

Dangerous
Safe
Dangerous
Safe

入力例 2

4 5
-2 7 -3 1
1 1 -2
1 2 6
2 3 4
3 4 -1
1 4 3

出力例 2

Dangerous
Safe
Dangerous
Safe
Dangerous

入力例 3

10 7
5 -4 8 0 -2 7 -6 3 1 -5
1 5 7
3 7 10
6 9 5
2 10 1
4 4 0
8 10 0
1 10 8

出力例 3

Dangerous
Safe
Dangerous
Dangerous
Dangerous
Safe
Safe

入力例 4

20 12
2 -1 3 5 -2 4 -3 6 -5 1 0 -4 7 -6 8 -7 9 -8 10 -9
1 4 9
5 10 1
7 13 2
12 20 5
1 20 10
14 19 7
15 17 10
2 18 8
8 8 6
9 12 -7
10 15 6
3 16 7

出力例 4

Dangerous
Dangerous
Dangerous
Safe
Dangerous
Safe
Dangerous
Safe
Dangerous
Safe
Dangerous
Dangerous

入力例 5

1 3
-10000
1 1 -2000000000
1 1 -10000
1 1 2000000000

出力例 5

Dangerous
Dangerous
Safe

Score : 333 pts

Problem Statement

Takahashi is planning a hiking course that passes through N points arranged in a straight line.

The temperature at the j-th point is A_j.

When walking from the L-th point to the R-th point, the heat load received over that section is defined as the sum of temperatures A_L + A_{L+1} + \cdots + A_R. If the heat load is at least the threshold K, it is judged as "dangerous"; if it is less than K, it is judged as "safe".

M plans are given. In the i-th plan, one walks from the L_i-th point to the R_i-th point. The threshold for this plan is K_i. For each plan, determine whether it is "dangerous" or "safe".

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 10^5
  • -10^4 \leq A_j \leq 10^4 （1 \leq j \leq N）
  • 1 \leq L_i \leq R_i \leq N （1 \leq i \leq M）
  • -2 \times 10^9 \leq K_i \leq 2 \times 10^9 （1 \leq i \leq M）
  • All input values are integers

Input

N M
A_1 A_2 \cdots A_N
L_1 R_1 K_1
L_2 R_2 K_2
\vdots
L_M R_M K_M
  • The first line contains the number of points N and the number of plans M, separated by a space.
  • The second line contains the temperatures at each point A_1, A_2, \ldots, A_N, separated by spaces.
  • The (2 + i)-th line (1 \leq i \leq M) contains the starting point L_i, ending point R_i, and threshold K_i of the i-th plan, separated by spaces.

Output

Output M lines.

On the i-th line, if A_{L_i} + A_{L_i+1} + \cdots + A_{R_i} \geq K_i for the i-th plan, output Dangerous; otherwise, output Safe.

Sample Input 1

5 4
3 1 4 1 5
1 3 8
2 4 7
4 5 6
5 5 10

Sample Output 1

Dangerous
Safe
Dangerous
Safe

Sample Input 2

4 5
-2 7 -3 1
1 1 -2
1 2 6
2 3 4
3 4 -1
1 4 3

Sample Output 2

Dangerous
Safe
Dangerous
Safe
Dangerous

Sample Input 3

10 7
5 -4 8 0 -2 7 -6 3 1 -5
1 5 7
3 7 10
6 9 5
2 10 1
4 4 0
8 10 0
1 10 8

Sample Output 3

Dangerous
Safe
Dangerous
Dangerous
Dangerous
Safe
Safe

Sample Input 4

20 12
2 -1 3 5 -2 4 -3 6 -5 1 0 -4 7 -6 8 -7 9 -8 10 -9
1 4 9
5 10 1
7 13 2
12 20 5
1 20 10
14 19 7
15 17 10
2 18 8
8 8 6
9 12 -7
10 15 6
3 16 7

Sample Output 4

Dangerous
Dangerous
Dangerous
Safe
Dangerous
Safe
Dangerous
Safe
Dangerous
Safe
Dangerous
Dangerous

Sample Input 5

1 3
-10000
1 1 -2000000000
1 1 -10000
1 1 2000000000

Sample Output 5

Dangerous
Dangerous
Safe