P9110 [PA 2020] Samochody dostawcze

**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 3 [Samochody dostawcze](https://sio2.mimuw.edu.pl/c/pa-2020-1/sam/)** Byteasar 是一家向商店运送物资的公司的后勤人员。在他公司所在的城市里，道路网由横向的街（从西到东）和纵向的道（从南到北）组成。每一对相邻的街和相邻的道都相距一公里。我们把街按从南到北的顺序编号，把道按从西到东的顺序编号。我们将第 $i$ 条道和第 $j$ 条街的交叉点记为 $(i,j)$。你可以假设，对于任何一个整数，都存在一条街的编号为 $j$ 和一条道的编号为 $i$。 Byteasar 明天安排了 $n$ 次送货；第 $i$ 次送货将由一辆货车在时刻 $t_i$ 离开车库，以每时间单位一公里的恒定速度沿街或道行驶。每次送货可以是两种类型中的一种：对于送货类型一，车库在路口 $(w_i,0)$，货车沿道 $w_i$ 向北行驶；对于送货类型二，车库在路口 $(0,w_i)$，货车沿街 $w_i$ 向东行驶。根据计划，每个车库在任何时刻最多只有一辆车离开。 货车不必停下来——驶过收货地点时，司机只需放下要送的包裹。然而，有一个问题，如果两辆货车发现他们同一时刻在同一个十字路口，就很可能会发生碰撞。Byteasar 非常希望避免这种情况。不幸的是，他唯一能做的就是取消一些送货计划。因此，他希望取消尽可能少的送货计划，以便剩下的车中没有任何两辆车同一时刻在同一个十字路口。

第一行一个整数 $n$，表示送货计划个数。 接下来 $n$ 行，每行三个整数 $r_i,w_i,t_i$，分别表示类型，车库位置和出发时间。

输出一个整数，表示最少取消的送货计划数。

#### 样例 1 解释 如果四份货物都送出，则第一和第二辆车会在时刻 $5$，在路口 $(5,3)$ 相撞。如果取消第一个送货计划，则第二和第四辆车会在时刻 $7$，在路口 $(7,3)$ 相撞。如果取消第二个送货计划，那么所有车都不会相撞了。 ------------ #### 数据范围 **本题采用捆绑测试** 对于 $100\%$ 的数据，保证 $1\le n\le 5\times 10^5$，$r_i\in \{1,2\}$，$1\le w_i\le 10^6$，$0\le t_i\le 10^6$。