(問題 13)車高制限 Scala編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
(問題)
ある高速道路は N 個の区間から成り立っています。i (1 ≦ i ≦ N) 番目の区間では天井は地上から A_i mのところにあり、地面は B_i mのところにあります。それぞれの区間において、道路の高さは A_i - B_i mで定義されます。それぞれの区間において車高が道路の高さ以下であるときのみ通行可能です。ここで、Q 個のクエリが与えられるので順番に処理してください。i (1 ≦ i ≦ Q) 番目のクエリは以下の通りです。
(ヒント) 一点加算はそれぞれ計算した後の結果に変更することで対処しましょう。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N
A_1 A_2 ... A_N
B_1 B_2 ... B_N
Q
q_1 a_1 b_1
q_2 a_2 b_2
...
q_Q a_Q b_Q
1 行目には 1 つの整数 N が与えられます。
2 行目には N 個の整数 A_1,A_2,...,A_N が与えられます。
3 行目には N 個の整数 B_1,B_2,...,B_N が与えられます。
4 行目には 1 つの整数 Q が与えられます。
4 + i (1 ≦ i ≦ Q) 行目には 3 つの整数 q_i,a_i,b_i が与えられます。
入力は合計 4 + Q 行からなり、入力値最終行の末尾に改行を 1 つ含みます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
q_i = 1 となる i の個数を q としたとき答えを q 行で出力してください。
j (1 ≦ j ≦ q) 行目には q_i = 1 となるクエリの中で j 番目のクエリの答えを出力してください。
- 条件
-
すべてのテストケースについて以下の条件を満たします。
- 1 ≦ N ≦ 200000
- 0 ≦ B_i ≦ A_i ≦ 10 ^ 9 (1 ≦ i ≦ N)
- 1 ≦ Q ≦ 200000
- 1 ≦ q_i ≦ 3 (1 ≦ i ≦ Q)
- q_i = 1 のとき、1 ≦ a_i ≦ b_i ≦ N (1 ≦ i ≦ Q)
- q_i = 1 でないとき、1 ≦ a_i ≦ N, 1 ≦ b_i ≦ 10 ^ 9 (1 ≦ i ≦ Q)
- すべての区間において常に道路の高さは 0 m以上
- q_i = 1 となる i が 1 つは存在する
- 入力例1
-
10
7 17 27 37 47 57 67 77 87 97
5 12 18 27 37 46 22 53 47 97
10
1 1 3
1 9 9
1 7 8
2 1 100
1 1 3
3 1 102
1 1 3
2 10 1000000000
2 9 1000000000
1 9 10
- 出力例1
-
2
40
24
5
0
1000000000
