[PA 2020] Samochody dostawcze

Luogu
IDLGP9110
Time2000ms
Memory256MB
DifficultyP2
2020PA(波兰)
**题目译自 [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 非常希望避免这种情况。不幸的是,他唯一能做的就是取消一些送货计划。因此,他希望取消尽可能少的送货计划,以便剩下的车中没有任何两辆车同一时刻在同一个十字路口。 ## Input 第一行一个整数 $n$,表示送货计划个数。 接下来 $n$ 行,每行三个整数 $r_i,w_i,t_i$,分别表示类型,车库位置和出发时间。 ## Output 输出一个整数,表示最少取消的送货计划数。 [samples] ## Note #### 样例 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$。
Samples
Input #1
4
1 5 2
2 3 0
2 3 6
1 7 4
Output #1
1
API Response (JSON)
{
  "problem": {
    "name": "[PA 2020] Samochody dostawcze",
    "description": {
      "content": "**题目译自 [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 是一家向商店运送物资的公司的后勤人员。在他公司所在的城市里,道路网由横向的街(从西到东)和纵向",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9110"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**题目译自 [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/)**\n\nByteasar 是一家向商店运送物资的公司的后勤人员。在他公司所在的城市里,道路网由横向的街(从西到东)和纵向...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments