#4182. 「ROI 2024 Day2」割草机的崛起

题目描述

译自 ROI 2024 Day2 T1. Восстание газонокосилок

在因诺波利斯市，草坪的修剪工作由电动机器人完成。可以将草坪看作是一条数线上的一段区域，机器人位于这条线的某些点上。机器人的体积可以忽略不计。草坪的最左端和最右端各有一个机器人，这两个位置之外没有草坪。每个机器人初始时面向左或面向右。

每个机器人的电量足以覆盖一定距离的草坪。夜间充电后，所有机器人会同时开始工作并以相同速度沿着直线移动。机器人将在以下三种情况下停止移动：

• 当机器人的电量耗尽，即从起点移动了其能覆盖的最大距离。
• 当机器人达到草坪的起始点或终点。
• 当机器人与迎面而来或已经停在那里的另一机器人在同一点相遇。

在机器人启动前，你可以改变一些机器人的行进方向。你的任务是确定，为了完全修剪整个草坪，需要改变多少机器人的方向。如果不能完成整个草坪的修剪，输出 $-1$。

---

输入格式

第一行包含一个整数 $n$ $(2 \leq n \leq 10^5)$，表示机器人的数量。

接下来 $n$ 行，每行描述一个机器人，包括三个整数 $x_i$, $p_i$, $d_i$，分别表示机器人的初始位置，它能覆盖的最大距离和它的初始朝向。其中 $d_i = -1$ 表示机器人向左（数值减小的方向），$d_i=1$ 表示机器人向右（数值增大的方向）。草坪的起始点和终点位于 $x_1=0$ 和 $x_n$。

---

输出格式

输出一个整数，表示需要改变方向的最小机器人数量以修剪整个草坪。如果无法完成任务，输出 $-1$。

---

样例 1

输入

3
0 1 -1
1 1 1
2 1 -1

输出

1

在这个样例中，通过改变中间机器人的方向，可以覆盖整个草坪。

---

样例 2

输入

2
0 1 1
4 2 -1

输出

-1

---

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 0 是样例。

子任务	分值	$n$ 的限制	附加限制	子任务依赖
1	23	$n \leq 10$	无	0
2	16	无	所有机器人初始朝向均为向右（即 $d_i =1$）	无
3	17	$n \leq 1000$	无	0,1
4	13	无	$x_i = i - 1$, $p_i = 1$	无
5	14		$p_i = 10^9$
6	17		无附加限制	0,1-5