0033 - Supercon2015予選問題

時間制限 1 秒 / メモリ制限 1024 MB / 得点 13 / Writer root / x 1 / 統計 /

TLE
1sec
MLE
1024MB
得点
13

SC 研究所では，独自に開発した通信システムを用いてロボットを制御する実験を行っている．実験は一直線上にある長さ L メートルの道路に沿って行われている．この道路上の位置を道路の左端からの長さ x（メートル）を用いて表す．

道路沿いには n 台の中継機 A1, A2,..., An があり，中継機 Ai は位置 xi に設置されている．また，中継機はそれぞれ固有のパワーを有しており，中継機 Ai のパワーは pi である．

一方，道路上には m 台のロボット B1, B2,..., Bm がいる．各ロボットには無線機が搭載されており，それが近くの中継機を通して我々と通信を行っている．これらの無線機の動作には特徴があり，ロボット Bj はつねに，その左右 zj メートル以内にある中継機のうち最大のパワーをもつもの（複数存在する場合は，そのうちのどれか）と通信を行う．この zj をロボット Bj の通信半径とよぶ．

さて，実験中に大規模な通信障害が発生し，すべてのロボットの位置情報がわからなくなってしまった．そんな中，かろうじて，ロボット Bj が現在通信している中継機のパワー qj の情報を割り出すことに成功した．この情報を使えば，ロボットたちの現在位置をある程度絞り込むことができるはずだ．あなたの仕事は，各ロボットについて，その存在可能範囲（現在位置としてありえる位置の範囲）の長さを求めることである．

入力

入力は、以下の形式で与えられる.

L n
x1 p1
x2 p2
.
.
.
xn pn
m
z1 q1
z2 q2
.
.
.
zm qm
  • 先頭の行には 2 つの整数 L, n が空白区切りで与えられ，それぞれ道路の長さと中継機の台数を表す．
  • 続く n 行は中継機の情報を表す．n 行のうち i（1 ≦ i ≦ n）行目には 2 つの整数 xi, pi が空白区切りで与えられ，それぞれ中継機 Aiの位置とパワーを表す．
  • つぎの行には，ロボットの台数を表す 1 つの整数 m が与えられる．
  • 続く m 行はロボットの情報を表す．m 行のうち j（1 ≦ j ≦ m）行目には 2 つの整数 zj, qj が空白区切りで与えられ，それぞれロボット Bj の通信半径と現在通信している中継機のパワーを表す．

出力

w1
w2
.
.
.
wm

出力は m 行からなる．m 行のうち j（1 ≦ j ≦ m）行目にはロボット　Bj の存在可能範囲の長さ wj（メートル）を 1 行に出力せよ．出力は標準出力に行い，末尾には改行を入れること．

制約

入力はすべて整数であり，以下の制約をみたす．

  • 1 ≦ n, m ≦ 3・105
  • 1 ≦ L, pi, zj, qj ≦ 109
  • 0 ≦ x1 < x2 < ... < xn ≦ L

ただし，2 級問題および 3 級問題では，より強い制約を追加する．

入力例

20 11
2 2
3 5
4 3
6 4
8 3
10 2
11 5
13 2
16 4
18 2
20 4
3
1 5
3 4
2 3

出力例

4
8
1

予選問題と級認定問題

問A（スーパコン 3 級問題）

上記の問題を解くプログラムを作成してください．ただし，入力は先述の制約に加えて

  • n, m, pi, qj ≦ 100
  • L, zj ≦ 1000

をみたす．

問B（スーパーコン 2 級問題）

上記の問題を解くプログラムを作成してください．ただし，入力は m = 1 をみたす．

問C（予選問題兼スーパーコン 1 級問題）

上記の問題を解くプログラムを作成してください．追加制約はありません．（注：予選問題とし ては例年より難しいため，最大ケース（n = m = 3・105）が制限時間内に解けなくても通過できる可能性は大いにあると予想しています．奮ってご応募ください！なお，非常に単純な例題をウェブに掲示しましたので，少なくともその例題で正しく動くかを確認した上で応募するようにして下さい．