@everyone 揪打CF
4454 . 油城西和他的難題庫
TopCoder
Description
油城西是一個毒瘤
身為一個毒瘤，他自然有很多難題可以砸人
現在他有 $n$ 個題庫，其中第 $i$ 個題庫包含了 $[l_i,r_i]$ 間所有整數難度的題目各一題
而現在也有 $q$ 個人依序想被題目砸
其中第$i$ 個人的實力值為 $s_i$
若一道題目的難度為 $x$ ，則我們定義該題目和第 $i$ 個人的適合度為 $|x - s_i|$
而每個人都會被分配到目前和他最適合的題目（也就是適合度數值最低的題目）
若有兩題的合適度相同，則油城西會拿比較難的題目砸他
同時為了避免題目慘遭外流
一道題目只要分配給一個人後就不能再分給別人了
請依序輸出每個人被分到的題目難度為多少
Input Format
$n$
$l_1$ $r_1$
$...$
$l_n$ $r_n$
$q$
$s_1$
$...$
$s_q$
Input Limits:
$n,q \leq 10^6$
$1 \leq l_1 \leq r_1 < l_2 \leq r_2 < ... < l_n \leq r_n \leq 10^{18}$
$\forall i, s_i \leq 10^{18}$
$q \leq \sum\limits^n_{i=1} r_i - l_i + 1$
所有輸入均為正整數
Output Format
輸出 $q$ 行正整數
Sample Input 1
5
1 2
6 7
9 12
24 24
41 50
4
14
24
24
4
1 2
6 7
9 12
24 24
41 50
4
14
24
24
4
Sample Output 1
12
24
11
6
24
11
6
Hints
Problem Source
Google Kickstart 2021 Round D
Subtasks
| No. | Testdata Range | Score |
|---|