2015.6.1

スーパーコン 2015 予選問題（ならびに級認定問題）「ロボットを探せ！」
SC 研究所では，独自に開発した通信システムを用いてロボットを制御する実験を行っている．
実験は一直線上にある長さ L メートルの道路に沿って行われている．この道路上の位置を道路の左端からの長さ x（メートル）を用いて表す．
道路沿いには n 台の中継機 A1 , A2 , . . . , An があり，中継機 Ai は位置 xi に設置されている．また，中継機はそれぞれ固有のパワーを有しており，中継機 Ai のパワーは pi である．
一方，道路上には m 台のロボット B1 , B2 , . . . , Bm がいる．各ロボットには無線機が搭載されており，それが近くの中継機を通して我々と通信を行っている．これらの無線機の動作には特徴があり，ロボット Bj はつねに，その左右 zj メートル以内にある中継機のうち最大のパワーをもつもの（複数存在する場合は，そのうちのどれか）と通信を行う．この zj をロボット Bj の通信半径とよぶ．
さて，実験中に大規模な通信障害が発生し，すべてのロボットの位置情報がわからなくなってしまった．そんな中，かろうじて，ロボット Bj が現在通信している中継機のパワー qj の情報を割り出すことに成功した．この情報を使えば，ロボットたちの現在位置をある程度絞り込むことができるはずだ．あなたの仕事は，各ロボットについて，その存在可能範囲（現在位置としてありえる位置の範囲）の長さを求めることである．

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



Ln
x1 p1
x2 p2..
.
xn pnmz1 q1z2 q2..
.
zm qm




• 先頭の行には 2 つの整数 L, n が空白区切りで与えられ，それぞれ道路の長さと中継機の台数を表す．
• 続く n 行は中継機の情報を表す．n 行のうち i（1 ≤ i ≤ n）行目には 2 つの整数 xi , pi が空白区切りで与えられ，それぞれ中継機 Ai の位置とパワーを表す．
• つぎの行には，ロボットの台数を表す 1 つの整数 m が与えられる．

1

• 続く m 行はロボットの情報を表す．m 行のうち j （1 ≤ j ≤ m）行目には 2 つの整数 zj , qjが空白区切りで与えられ，それぞれロボット Bj の通信半径と現在通信している中継機のパワーを表す．

出力
w1w2..
.

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 112 23 54 36 48 3
10 211 513 216 418 220 431 53 42 3
2

図 1 の矢印は中継機を表し，上に書かれている数字はそのパワーを表している．ここでは，

A1 , A2 , . . . , A11 の 11 台が設置されている．

A25A44A33A12A75A5350A114A94A62A102A82101520

図 1: 入力例における中継機の配置
一方，ロボットは B1 , B2 , B3 の 3 台おり，その通信半径はそれぞれ z1 = 1, z2 = 3, z3 = 2 である．
いま，各ロボットが現在通信している中継機のパワーがそれぞれ q1 = 5，q2 = 4，q3 = 3 であることがわかっている．このとき，各ロボットの存在可能範囲はどのようになるだろうか？
まず，B1 について考えてみよう．B1 は現在パワー 5 の中継機と通信しているから，その存在可能範囲は図 2 の灰色帯の範囲，2 ≤ x ≤ 4, 10 ≤ x ≤ 12 であることがすぐにわかる．したがって，答えは w1 = (4 − 2) + (12 − 10) = 4 となる．

A25A75↓ 䛣䛾఩⨨䛿୙ྍ⬟↓ 䛣䛾఩⨨䛿୙ྍ⬟+0+311

図 2: ロボット B1 の存在可能範囲：z1 = 1, q1 = 5 なので灰色の帯の部分が存在可能範囲

B2 , B3 はもう少し複雑だ．たとえば B2 は x = 6 の位置にはいない．その位置だと中継機 A2（パワー 5）と交信しているはずだからである．同様に 8 ≤ x ≤ 14 の位置もあり得ない．そう考えると，
B2 の存在可能範囲は 6 < x < 8, 14 < x ≤ 20 となる．したがって，答えは w2 = (8−6)+(20−14) = 8となる．

A25A44+
3A75䛣䛾఩⨨䛿୙ྍ⬟

116A94A114↓ 䛣䛾఩⨨䛿୙ྍ⬟+1620

図 3: ロボット B2 の存在可能範囲：z2 = 3, q2 = 4 なので灰色の帯の部分が存在可能範囲

3B3 となると，存在可能範囲は 8 < x < 9 のみである．したがって，答えは w3 = 9 − 8 = 1 となる．

A25A33A44A75A53 ↓ 䛣䛾఩⨨䛿୙ྍ⬟

A94A1141620+0346811

図 4: ロボット B3 の存在可能範囲：z3 = 2, q3 = 3 なので灰色の帯の部分が存在可能範囲
したがって，入力例に対する正しい出力は以下のようになる．

出力例

481



予選問題と級認定問題
問 A（スーパーコン 3 級問題）
上記の問題を解くプログラムを作成してください．ただし，入力は先述の制約に加えて• n, m, pi , qj ≤ 100• L, zj ≤ 1000をみたす．

問 B（スーパーコン 2 級問題）
上記の問題を解くプログラムを作成してください．ただし，入力は m = 1 をみたす．

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

【応募にあたっての注意】

1. 作成するプログラム(a) 標準入力から入力を受け取り，標準出力に答えを出力するプログラムを作成してください．そうでないプログラム，たとえば答えをファイルに出力するプログラムを提出した場合，そのプログラムは採点対象外となってしまいます．くれぐれも注意してください．
（標準入出力について不安な場合には，たとえば，ウェブにあるテンプレート template.c を参考にしてください．
）(b) 提出するプログラムは指定したファイル名の単一ファイルとしてください．
(c) プログラムは C 言語で記述してください．詳細は以下の通りです．
・ プログラムは C 言語規格に準拠する C 言語で記述してください．
（インラインアセンブラの使用は禁止します．
）
・ int は 32 ビット，long long は 64 ビットを仮定します．long のビット幅は環境により異なるので，64 ビット整数を扱いたい場合は long ではなく long long を使用してください．
（<stdint.h> をインクルードして，int64_t を使用してもよい．
）
・ Mac OS X 上の Homebrew gcc49 4.9.2 1 でコンパイルし，Mac OS X 上で実行します．
コンパイルにはつぎのコマンドを使用します: gcc -g -O2 -std=gnu99 -static $* -lm
・ 移植性の問題（たとえばエンディアンの違い）によるトラブルには対処しません．

2. 審査方法（予選選抜に関して）(a) 応募プログラムをコンパイルし，30 題程度の問題例に対して各々1 分間の制限時間で実行します．
(b) メモリ使用量は 1 ギガバイトに制限します．具体的には，ulimit -d 1000000 -m 1000000-v 1000000 のもとで実行します．
(c) 制限時間内に正確な答えを出している問題例の個数が多い方が上位となります．
(d) 同順位のチームに対しては，正解した問題例に対する計算時間の合計が短い方が上位となります．
（万が一，なお同順位のチームが存在した場合，提出されたプログラムの説明をもとに工夫度を評価して順位を決定します．
）(e) 以上の規則のもとで，東西上位 10 チームずつを本選出場候補チームとして選出します．ただし，1 校からは最大 2 チームしか本戦出場できません．
3. 審査方法（スーパーコン認定に関して）(a) 応募プログラムをコンパイルし，各級の追加制約をみたす 10 題程度の問題例に対して各々1分間の制限時間で実行し，すべての問題例で制限時間内に正確な答えを出している場合に合格とします．
(b) メモリ使用量は 1 ギガバイトに制限します．具体的には，ulimit -d 1000000 -m 1000000-v 1000000 のもとで実行します．

5