Trapped in the Haybales (Gold)

题目描述

农夫约翰收到了一批 $N$ 个巨大的干草捆（\n$1 \le N \le 100,000$\n），并把它们放在通往谷仓的道路沿线的不同位置。\n不幸的是，他完全忘了奶牛贝茜正在路边吃草，现在她可能被这些干草捆困住了！\n每个干草捆 $j$ 有一个大小 $S_j$ 和一个位置 $P_j$，表示它在一维道路上的位置。奶牛贝茜可以在道路上自由移动，甚至可以移动到某个干草捆所在的位置，但她不能穿过该位置。作为例外，如果她朝同一方向连续奔跑 $D$ 的距离，她会积累足够的速度，撞穿并永久清除任何大小严格小于 $D$ 的干草捆。当然，在这样做之后，她可能会打开更多空间，使她能够再去冲刺其他干草捆并将其清除。\n如果贝茜最终能够撞穿最左边或最右边的干草捆，她就可以逃到自由。请计算道路上所有实数起始位置中，贝茜无法逃脱的那些位置所组成的总长度（面积）。

输入格式

第一行输入 $N$。接下来的 $N$ 行每行描述一个干草捆，包含两个整数，分别表示其大小和位置，二者都在范围 $1\ldots 10^9$ 内。所有位置互不相同。

输出格式

输出一个整数，表示贝茜无法逃脱的道路长度（面积）。

5\n8 1\n1 4\n8 8\n7 15\n4 20

14

提示

[题目署名：Brian Dean, 2015]

标签: USACO|2015|Gold

来源

USACO|2015|Gold