Solution

发现有一个明显的结论：在可行的方案中，要么所有机器人方向一致，要么存在 $i\in[1,n)$，满足 $1$ 至 $i$ 号机器人向右，$i+1$ 至 $n$ 号机器人向左。

怎么证呢？假设存在两个机器人 $i$，$i+1$（已按 $x$ 排序），$i$ 向左，$i+1$ 向右。那么 $x_i$ 到 $x_{i+1}$ 是必然无法被经过的，故假设不成立，结论成立。

当所有机器人方向向左时，方案可行当且仅当对于任意 $i\in[1,n)$ 满足 $x_{i+1}-x_i\le p_i$，向右同理。

当机器人存在两种方向时，枚举断点再进行类似的判断即可。这里有个坑点，断点 $i$ 与 $i+1$ 间只需满足 $x_{i+1}-x_i\le p_{i+1}+p_i$ 即可，而非 $x_{i+1}-x_i\le p_{i+1}$ 且 $x_{i+1}-x_i\le p_i$，因为二者进行的是相向运动，画个图就明白了。

在每次枚举断点的过程中判断，时间复杂度为 $O(n^2)$ 无法通过，可以使用前缀和优化至 $O(n)$。

Code

#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define INF 1e18
using namespace std;
int n,ans=INF,a[N],b[N],c[N],s1[N],s2[N],l[N],r[N];
signed main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i]>>c[i];
		s1[i]=s1[i-1];
		if(c[i]==-1) s1[i]++;
		if(i==1) continue;
		if(a[i]-a[i-1]<=b[i-1]) l[i-1]++;
		l[i]=l[i-1]+(i==n);
	}
	for(int i=n;i>=1;i--){
		s2[i]=s2[i+1],r[i]=r[i+1];
		if(c[i]==1) s2[i]++;
		if(i==1||a[i]-a[i-1]<=b[i]) r[i]++;
	}
	if(l[n]==n) ans=min(ans,s1[n]);
	if(r[1]==n) ans=min(ans,s2[1]);
	for(int i=1;i<n;i++){
		if(l[i-1]!=i-1||r[i+2]!=n-i-1||a[i+1]-a[i]>b[i+1]+b[i]) continue;
		ans=min(ans,s1[i]+s2[i+1]);
	}
	cout<<(ans==INF?-1:ans);
	return 0;
}