点の幅
(paizaランク A 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
テストの返却中に暇だった paiza 君は、また 2 人で遊ぶゲームを思いつきました。
「2 人はそれぞれ生徒番号 1 〜 N の全校生徒 N 人の中から生徒番号が連続するように好きな人数の生徒を選ぶ。その選んだ生徒達の得点の幅が大きい方、すなわちその生徒たちの (最高点 - 最低点) の値が大きい方が勝ち、同じだったら引き分け！」
「ただし、このルールだと人を多く選ぶ方が有利になってしまうから、選べる生徒の数はお互い N/2 人以下ね！」
また審判を任されたあなたは、全ての生徒の得点を記録しておくことで、選んだ生徒たちの最小・最大の生徒番号を確認するだけで、その生徒たちの中の (最高点 - 最低点) の値をすぐに求めることができることに気付きました。
学校の生徒数 N と試合の数 K , 各生徒の得点 S_1 ... S_N と、
i 番目の試合で対戦した A と B の 2 人が選んだ生徒の最小の生徒番号と最大の生徒番号が与えられるので、各試合のジャッジをしてください。
- 入力される値
-
N K
S_1
...
S_N
A_{l_1} A_{r_1} B_{l_1} B_{r_1}
...
A_{l_K} A_{r_K} B_{l_K} B_{r_K}
・1 行目では、生徒数 N とおこなわれる試合数 K が与えられます。
・続く N 行のうち、i 行目では、生徒番号 i の生徒のテストの得点 S_i が与えられます。
・続く K 行のうち、i 行目では、i 試合目のプレイヤー A が選んだ生徒のうち、最小の生徒番号と最大の生徒番号 A_{l_i} , A_{r_i} とプレイヤー B が選んだ生徒のうち、最小の生徒番号と最大の生徒番号 B_{l_i} , B_{r_i} が与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
ans_1
...
ans_K
・i 行目に i 試合目の結果を出力してください。
A の勝ちの場合は 'A', B の勝ちの場合は 'B' , 引き分けの場合は 'DRAW' と出力してください。
・また、出力の末尾には改行を入れてください。
- 条件
-
・1 ≦ N ≦ 10,000
・N は平方数である(ある整数 x > 0 を用いて N = x^2 と表すことができる)
・1 ≦ K ≦ 100,000
・0 ≦ S_i ≦ 100,000 (1 ≦ i ≦ N)
・1 ≦ Al_i ≦ Ar_i ≦ N (1 ≦ i ≦ K)
・1 ≦ Bl_i ≦ Br_i ≦ N (1 ≦ i ≦ K)
・各ゲームにおいて、プレイヤーの選ぶ生徒の数は N/2 以下であることが保証されている。
- 入力例1
-
4 2
1
3
2
4
1 2 2 3
1 2 3 4
- 出力例1
-
A
DRAW
- 入力例2
-
25 5
82336
23137
58263
78843
86854
90102
60652
35458
68587
20899
85950
20509
74628
71306
72676
70046
2492
20827
62047
4805
27067
5411
29873
37553
91148
6 11 11 14
13 15 12 13
2 3 17 19
1 8 13 18
6 10 15 16
- 出力例2
-
A
B
B
B
A
