Apple Catching

题目描述

苹果雨来啦！在某些时刻，会有若干苹果落到数轴上。在某些时刻，农夫约翰的一些奶牛会到达数轴并开始接苹果。 如果一个苹果落到数轴时没有奶牛能接到它，那么它将永远丢失。 如果一头奶牛和一个苹果同时到达，那么奶牛会接住它。每头奶牛每秒可以移动 1 个单位距离。一旦一头奶牛接到一个苹果，她就会离开数轴。 如果农夫约翰的奶牛进行最优协作，总共最多能接到多少个苹果？

输入格式

第一行包含 $N$（$1\le N\le 2\cdot 10^5$），表示苹果落下或奶牛出现的事件次数。 接下来 $N$ 行每行包含四个整数 $q_i$, $t_i$, $x_i$, $n_i$（$q_i\in \{1,2\}, 0\le t_i\le 10^9, 0\le x_i\le 10^9, 1\le n_i\le 10^3$）。 如果 $q_i=1$，表示有 $n_i$ 头奶牛在时刻 $t_i$ 到达数轴上的位置 $x_i$。 如果 $q_i=2$，表示有 $n_i$ 个苹果在时刻 $t_i$ 落到数轴上的位置 $x_i$。 保证所有有序对 $(t_i,x_i)$ 两两不同。

输出格式

输出农夫约翰的奶牛合计最多能接到的苹果数量。

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

10

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

9

提示

在这个例子中，落在时刻 $t=5$ 的 $100$ 个苹果都无法被接到。下面是一种接到 $10$ 个苹果的方法： 在时刻 $t=4$ 到达的 6 头奶牛都去接在时刻 $t=8$ 落下的苹果。 在时刻 $t=2$ 到达的奶牛中，有 1 头去接在时刻 $t=8$ 落下的苹果。 在时刻 $t=2$ 到达的剩余奶牛中，有 3 头去接在时刻 $t=6$ 落下的苹果。

同样地，落在时刻 $t=5$ 的苹果都无法被接到。此外，在时刻 $t=2$ 到达的奶牛无法接到任何在时刻 $t=8$ 落下的苹果。下面是一种接到 $9$ 个苹果的方法： 在时刻 $t=4$ 到达的 6 头奶牛都去接在时刻 $t=8$ 落下的苹果。 在时刻 $t=2$ 到达的剩余奶牛中，有 3 头去接在时刻 $t=6$ 落下的苹果。

题目来源：Benjamin Qi

标签: USACO|2022|Gold

来源

USACO|2022|Gold