← 返回题目列表

Codeforces · 1545/E1

E1. AquaMoon 和 Time Stop(简单版)

中文机器翻译题面 查看原题

请注意,简单版和困难版之间的区别在于 $$$n$$$ 的限制和时间限制。只有两个版本都解决了,你才能进行黑客攻击。

水月有先见之明,知道有鬼魂想要在步行街上诅咒游客。但可惜的是,这一次,这些鬼魂都隐藏在结界之中,她无法短时间内进入这个结界,将它们消灭掉。因此,我们能做的就是从鬼魂手中拯救街上任何不幸的人。

步行街可以表示为一维坐标系。步行街上有一个人闲逛。此时$$$0$$$他位于坐标$$$x$$$处,以每秒$$$1$$$单位的速度移动。特别是,在时间 $$$i$$$ 时,该人将位于坐标 $$$x+i$$$ 处。

鬼魂将在街上施放 $$$n$$$ 诅咒。第 $$$i$$$ 诅咒将从 $$$tl_i-1+10^{-18}$$$ 持续到 $$$tr_i+1-10^{-18}$$$(仅),并且会杀死坐标从 $$$l_i-1+10^{-18}$$$ 到 $$$r_i+1-10^{-18}$$$(仅)的人。从形式上来说,这意味着,在 $$$(tl_i-1+10^{-18},tr_i+1-10^{-18})$$$ 时间范围内坐标位于 $$$(l_i-1+10^{-18},r_i+1-10^{-18})$$$ 之间的人将会死亡。

为了拯救街上的人,AquaMoon可以随时停止时间$$$t$$$,然后将人从当前坐标$$$x$$$移动到任意坐标$$$y$$$($$$t$$$、$$$x$$$和$$$y$$$不一定是整数)。该运动会消耗 AquaMoon $$$|x-y|$$$ 能量。运动是连续的,所以如果在$$$t$$$时刻$$$x$$$和$$$y$$$之间存在一些诅咒区域,这个人也会死。

AquaMoon 想知道她需要花费多少能量才能将街上的人从所有 $$$n$$$ 诅咒中拯救出来。但她不擅长编程。作为她的朋友,你能帮助她吗?

输入

第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2000$$$) — 诅咒的数量。

下一行包含一个整数 $$$x$$$ ($$$1\le x\le 10^6$$$) — 人的初始坐标。

以下 $$$n$$$ 行包含四个整数 $$$tl_i$$$、$$$tr_i$$$、$$$l_i$$$、$$$r_i$$$ ($$$1\le tl_i\le tr_i\le 10^6$$$、$$$1\le l_i\le r_i\le 10^6$$$)。

输出

打印一个整数 - AquaMoon 需要消耗的最小能量,四舍五入到最接近的整数(如果有两个最接近的整数,您应该将答案四舍五入到其中最高的整数)。

示例

输入 #1

2
1
1 2 1 2
2 3 2 3

输出 #1

2

输入 #2

3
4
1 4 1 2
1 4 4 15
6 7 1 4

输出 #2

8

输入 #3

4
3
1 5 1 1
4 10 1 4
1 2 3 13
1 10 7 19

输出 #3

14

输入#4

7
5
78 96 76 91
6 16 18 37
53 63 40 56
83 88 21 38
72 75 17 24
63 63 53 60
34 46 60 60

输出#4

20