P9110 [PA 2020] Delivery Trucks

**This problem is translated from [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Round 3 [Samochody dostawcze](https://sio2.mimuw.edu.pl/c/pa-2020-1/sam/).** Byteasar is a logistics worker in a company that delivers goods to shops. In the city where his company is located, the road network consists of horizontal streets (from west to east) and vertical avenues (from south to north). Every pair of neighboring streets and neighboring avenues is $1$ kilometer apart. We number the streets from south to north, and the avenues from west to east. We denote the intersection of avenue $i$ and street $j$ as $(i,j)$. You may assume that for every integer, there exists a street numbered $j$ and an avenue numbered $i$. Byteasar has scheduled $n$ deliveries for tomorrow. For the $i$-th delivery, a truck leaves its depot at time $t_i$ and moves at a constant speed of $1$ kilometer per unit time, traveling only along streets or avenues. Each delivery is of one of two types: - For type $1$, the depot is at intersection $(w_i,0)$, and the truck goes north along avenue $w_i$. - For type $2$, the depot is at intersection $(0,w_i)$, and the truck goes east along street $w_i$. According to the schedule, from any depot, at most one truck departs at any time. The truck does not have to stop: when passing the destination intersection, the driver only needs to drop off the package. However, there is a problem: if two trucks find themselves at the same intersection at the same time, a collision is very likely. Byteasar really wants to avoid this. Unfortunately, the only thing he can do is cancel some deliveries. Therefore, he wants to cancel as few deliveries as possible so that among the remaining trucks, no two are ever at the same intersection at the same time.

The first line contains an integer $n$, the number of delivery plans. The next $n$ lines each contain three integers $r_i,w_i,t_i$, representing the type, the depot position, and the departure time, respectively.

Output one integer, the minimum number of delivery plans that must be canceled.

#### Explanation of Sample 1 If all four deliveries are carried out, then the first and second trucks will collide at time $5$ at intersection $(5,3)$. If the first delivery plan is canceled, then the second and fourth trucks will collide at time $7$ at intersection $(7,3)$. If the second delivery plan is canceled, then no trucks will collide. ------------ #### Constraints **This problem uses bundled testdata.** For $100\%$ of the testdata, it is guaranteed that $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$. Translated by ChatGPT 5