(問題 15)遊園地の案内人 F#(Beta)編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
(問題)
ジェットコースターに N 組のグループが並んでいます。前から i (1 ≦ i ≦ N) 番目のグループは A_i 人です。
回転率を上げるため、ジェットコースターにはできるだけ多くの客を載せたいですが、順番を入れ替えたり同じグループの人を別々に案内することはできません。
Q 個のクエリが与えられるので順番に処理してください。i 番目のクエリは以下の通りです。
なお、q_i = 2 のクエリはそれぞれのクエリ限定で他のクエリには影響を及ぼさないものとします。
(ヒント)問題 14 でやったように二分探索で考えましょう。更新があるため問題 14 のように累積和を使うことはできないので判定問題を高速に解く方法を考えましょう。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N
A_1 A_2 ... A_N
Q
q_1 I_1 X_1
q_2 I_2 X_2
...
q_Q I_Q X_Q
1 行目には 1 つの整数 N が与えられます。
2 行目には N 個の整数 A_1,A_2,...,A_N が与えられます。
3 行目には 1 つの整数 Q が与えられます。
3 + i (1 ≦ i ≦ Q) 行目には 3 つの整数 q_i,I_i,X_i が与えられます。
入力は合計 3 + Q 行からなり、入力値最終行の末尾に改行を 1 つ含みます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
q_i = 2 となる i の個数を q としたとき、答えを q 行で出力してください。
j (1 ≦ j ≦ q) 行目には q_i = 2 となるクエリの中で j 番目のクエリの答えを出力してください。
- 条件
-
すべてのテストケースについて以下の条件を満たします。
- 1 ≦ N ≦ 20000
- 1 ≦ A_i ≦ 10 ^ 9 (1 ≦ i ≦ N)
- 1 ≦ Q ≦ 20000
- 1 ≦ q_i ≦ 2 (1 ≦ i ≦ Q)
- 1 ≦ I_i ≦ N (1 ≦ i ≦ Q)
- 1 ≦ X_i ≦ 10 ^ (9 × q_i) (1 ≦ i ≦ Q)
- 入力例1
-
10
1 5 7 9 10 12 3 5 1 7
10
2 1 15
1 2 15
2 1 15
2 4 1
1 8 1
1 7 1
1 10 1
2 5 26
2 7 1
2 1 1000000000
- 出力例1
-
3
1
0
6
1
10
