让时间倒流，假设时刻 \(0\) 偷钻石 \(2\)，时刻 \(d\) 偷钻石 \(1\)。
对于 \(t=1,2\) 的摄像头，关掉它的时间区间已确定。对于每个 \(t=3\) 的摄像头，它有 \(2\) 种选择：
- 在 \([d+1,s]\) 内关掉
- 分别在 \([1,s],[d+1,d+s]\) 内关掉
注意每个区间的左端点 \(\in \{1,d+1\}\)。若已决定怎么选，根据 Hall 定理，不合法 \(\Lrarr\) 出现下面至少 \(1\) 种情况：
- \(\exists r, [d+1,r]\) 内需关掉 \(>r-d\) 个摄像头
- 把偷钻石 \(1\) 看作加一个区间 \([d,d]\) 后，\(\exists r, [1,r]\) 内需关掉 \(> r\) 个摄像头。
先默认 \(t=3\) 都在 \([d+1,s]\) 内关掉。每次，找到 \(\min r\) 使得 \([d+1,r]\) 内需关掉 \(>r-d\) 个摄像头。此时要选一个区间内的 \(t=3\) 摄像头，把它改成 \([1,s],[d+1,d+s]\)。可以发现，选择的 \(s\) 越大，Hall 定理的 \(2\) 个限制都越容易满足。扫描 \(r\) 的同时维护区间内 \(t=3\) 的 \(s\) 构成的栈，每次取栈顶即可。
如此扫一遍，若 Hall 定理的第 \(1\) 条满足，直接判一遍第 \(2\) 条即可。这是因为改掉任意 \(t=3\) 后，第 \(2\) 条限制都会更紧。因此问题得到解决，一开始枚举 \(d\)，每次扫 \(2\) 遍，时间复杂度 \(O(n^2)\)。
#include<bits/stdc++.h>
#define rp(i,a,b) for(int i=a;i<=b;++i)
#define pr(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
const int inf=1e9;
const int N=1505;
int n,ac,a[N],bc,b[N],cc,c[N],cnt[2*N],tw[N],sc,st[N];
int solve(int d){
rp(i,0,2*n)cnt[i]=0;
rp(i,1,cc)tw[i]=0;
rp(i,1,cc){
++cnt[max(0,c[i]-d-1)];
}
rp(i,1,ac){
++cnt[a[i]];
}
sc=0;
int j=1;
rp(i,0,2*n){
for(;j<=cc&&c[j]-d-1<=i;++j){
st[++sc]=j;
}
if(i){
cnt[i]+=cnt[i-1];
}
while(cnt[i]>i){
if(!sc||c[st[sc]]<=i){
return inf;
}
--cnt[i];
++cnt[c[st[sc]]];
tw[st[sc--]]=1;
}
}
rp(i,0,2*n)cnt[i]=0;
int ret=n+2;
auto fun=[&](int x){
return x>d?x-1:x;
};
rp(i,1,ac){
++cnt[min(2*n,d+a[i])];
}
rp(i,1,bc){
++cnt[min(2*n,fun(b[i]))];
}
rp(i,1,cc){
++cnt[min(2*n,fun(c[i]))];
if(tw[i]){
++ret;
++cnt[min(2*n,d+c[i])];
}
}
rp(i,1,2*n){
cnt[i]+=cnt[i-1];
}
rp(i,0,2*n)if(cnt[i]>i){
return inf;
}
return ret;
}
int main(){
scanf("%d",&n);
rp(i,1,n){
int t,s;
scanf("%d%d",&t,&s);
switch(t){
case 1:
a[++ac]=s;
break;
case 2:
b[++bc]=s;
break;
case 3:
c[++cc]=s;
}
}
sort(c+1,c+cc+1);
int ans=inf;
rp(d,0,n)ans=min(ans,solve(d));
printf("%d\n",ans==inf?-1:ans);
return 0;
}