UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4249. Walls 防壁

统计 下载数据

Description

你入手了一款JOI社发售的游戏。你对这款游戏十分上手,每天玩得不亦乐乎。
某一天,玩家之中出现了一个叫做“镭射”的关卡。这个关卡十分的难,连老司机玩家也只有很低的概率才能通过。正在三番五次挑战这个关卡的你,很快判断出通过的可能性是存在的,并考虑写一个程序来计算出对策。
镭射关卡在一个配置有N个防壁的地形上进行。地形为长方形,分成了一些1*1的正方形区域。每个区域可以用两个非负整数(x,y)表示,左下角的区域为(0,0),(x,y)表示(0,0)往右数x个区域,再往上数y个区域的位置。
关卡开始后,敌人会出现并顺次进行M轮攻击。第i次攻击时,敌人将会从区域(Pi,N+1)向区域(Pi,0)进行直线镭射射击。
每个防壁放在y坐标相同的一些连续的区域中。防壁i(1<=i<=N)是左右长度为Bi-Ai+1,上下宽度为1的长方形,初始位置为(Ai,i)到(Bi,i)的所有区域。在敌人开始攻击之前以及两次攻击的间隙,你可以任意次地左右移动防壁。一次移动可以让防壁向右移动一个区域,或者向左移动一个区域。
镭射在穿过一个防壁后威力会减少。现在为了将镭射的威力最小化,需要移动防壁使得镭射能穿过所有的防壁。你想让移动防壁的次数尽量少。
现在给出关卡开始时每个防壁的位置,以及每个敌人的攻击位置,为了让每一发镭射都穿过所有的防壁,请你输出每个防壁移动次数的最小值。

Input

 第一行两个空格分隔的整数N,M,表示这个关卡有N个防壁,敌人将会进行M轮攻击。

接下来N行,第i行(1<=i<=N)有两个空格分隔的整数Ai,Bi,表示关卡开始时防壁i被放置在(Ai,i)到(Bi,i)的所有区域的位置上。
接下来M行,第i行有一个整数Pi,表示第i次攻击时,敌人从(Pi,N+1)向(Pi,0)进行直线镭射射击。

Output

 输出N行,第i行表示防壁i的移动次数的最小值。

Sample Input

4 4
0 3
4 4
2 7
8 11
6
4
3
8

Sample Output

5
10
1
7

Hint

1<=N<=2*10^5

1<=M<=2*10^5

0<=Ai<=Bi<=10^9 (1<=i<=N)

0<=Pi<=10^9 (1<=i<=M)

Source

JOI 2014~2015 春季training合宿 竞技4 By POPOQQQ