通信障害の調査
(paizaランク S 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
クライアント 0, 1, ..., n を直線状につなぐネットワークがあり、各クライアントは n 個の通信ケーブルによって接続されています。
paiza 君は、このネットワークで発生した通信障害を調査することになりました。
i 番目の通信ケーブル (ケーブル i) は、クライアント (i - 1) とクライアント i の間をつないでおり、時刻 0 における通信速度は s_i です。
また、時刻 1 から t までの各時刻 j において、ケーブル c_j の通信速度が d_j だけ低下したことがわかっています。
以下の q 個のクエリに答えてください。
i 番目のクエリでは、a_i, b_i, x_i が与えられるので、クライアント a_i とクライアント b_i の間の通信速度が x_i 以下になった最初の時刻を求めてください。
ただし、クライアント a_i とクライアント b_i の間の通信速度は、通信ケーブル a_i + 1, a_i + 2, ..., b_i の通信速度の最小値とします。
- 入力される値
-
n t q
s_1 s_2 ... s_n
c_1 d_1
c_2 d_2
...
c_t d_t
a_1 b_1 x_1
a_2 b_2 x_2
...
a_q b_q x_q
・ 1 行目には、通信ケーブルの数 n, 通信速度の低下が発生した時刻の数 t, クエリの数 q がこの順に半角スペース区切りで与えられます。
・ 2 行目には、通信ケーブルの時刻 0 における通信速度 s_1, s_2, ..., s_n がこの順に半角スペース区切りで与えられます。
・ 続く t 行には、時刻 j における通信速度の低下が発生した通信ケーブル c_j と、その通信速度の低下量 d_j がこの順に半角スペース区切りで与えられます。(1 ≦ j ≦ t)
・ 続く q 行には、i 番目のクエリのパラメータ a_i, b_i, x_i がこの順に半角スペース区切りで与えられます。(1 ≦ i ≦ q)
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
q 行出力してください。
i 行目には、i 番目のクエリの答えを整数で出力してください。
ただし、クライアント a_i とクライアント b_i の間の通信速度が時刻 0 の時点で x_i 以下である場合は、0 を出力してください。
また、クライアント a_i とクライアント b_i の間の通信速度が x_i 以下になる時刻が存在しない場合は、-1 を出力してください。
末尾に改行を入れ、余計な文字を含んではいけません。
- 条件
-
・ 2 ≦ n ≦ 1000 = 10^3
・ 1 ≦ t ≦ 1000 = 10^3
・ 1 ≦ q ≦ 100000 = 10^5
・ 1 ≦ s_i, d_i, x_i ≦ 1000000000 = 10^9
・ 1 ≦ c_j ≦ n
・ 0 ≦ a_i < b_i ≦ n
・ 通信速度の低下量の合計はそれぞれ s_i 未満である
・ 入力はすべて整数
- 入力例1
-
4 4 4
5 5 5 5
1 3
3 2
4 4
2 1
0 4 5
2 3 3
1 4 1
0 1 1
- 出力例1
-
0
2
3
-1
