#4249. Walls 防壁

Walls 防壁

题目描述

你入手了一款 JOI 社发售的游戏。你对这款游戏十分上手,每天玩得不亦乐乎。

某一天,玩家之中出现了一个叫做“镭射”的关卡。这个关卡十分的难,连老司机玩家也只有很低的概率才能通过。正在三番五次挑战这个关卡的你,很快判断出通过的可能性是存在的,并考虑写一个程序来计算出对策。

镭射关卡在一个配置有 nn 个防壁的地形上进行。地形为长方形,分成了一些 1×11 \times 1 的正方形区域。每个区域可以用两个非负整数 (x, y)(x,~y) 表示,左下角的区域为 (0, 0)(0,~0)(x, y)(x,~y) 表示 (0, 0)(0,~0) 往右数 xx 个区域,再往上数 yy 个区域的位置。

关卡开始后,敌人会出现并顺次进行 mm 轮攻击。第 ii 次攻击时,敌人将会从区域 (Pi, n+1)(P_i,~n+1) 向区域 (Pi, 0)(P_i,~0) 进行直线镭射射击。

每个防壁放在 yy 坐标相同的一些连续的区域中。防壁 ii 是左右长度为 BiAi+1B_i-A_i+1,上下宽度为 11 的长方形,初始位置为 (Ai, i)(A_i,~i)(Bi, i)(B_i,~i) 的所有区域。在敌人开始攻击之前以及两次攻击的间隙,你可以任意次地左右移动防壁。一次移动可以让防壁向右移动一个区域,或者向左移动一个区域。

镭射在穿过一个防壁后威力会减少。现在为了将镭射的威力最小化,需要移动防壁使得镭射能穿过所有的防壁。你想让移动防壁的次数尽量少。

现在给出关卡开始时每个防壁的位置,以及每个敌人的攻击位置,为了让每一发镭射都穿过所有的防壁,请你输出每个防壁移动次数的最小值。

输入格式

第一行两个空格分隔的整数 n, mn,~m,表示这个关卡有 nn 个防壁,敌人将会进行 mm 轮攻击。

接下来 nn 行,第 ii 行有两个空格分隔的整数 Ai, BiA_i,~B_i,表示关卡开始时防壁 ii 被放置在 (Ai, i)(A_i,~i)(Bi, i)(B_i,~i) 的所有区域的位置上。

接下来 mm 行,第 ii 行有一个整数 PiP_i,表示第 ii 次攻击时,敌人从 (Pi, n+1)(P_i,~n+1)(Pi, 0)(P_i,~0) 进行直线镭射射击。

输出格式

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

4 4
0 3
4 4
2 7
8 11
6
4
3
8
5
10
1
7

提示

$1 \le n,m \le 2 \times 10^5,~0 \le A_i \le B_i \le 10^9,~0 \le P_i \le 10^9$

题目来源

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