ABC 433 C

OIer_sundingjia · 2025-12-01 11:21:05 · 题解

忘了是哪一次 CF 原题了。

我们发现在一个时间节点上，高桥能飞到的地方是一个连续的区间。

在刚开始时，这个区间是 [H,H]。

高桥每水平往前走一个单位，他最多竖直移动一个单位。

所以高桥往前移动 T 各单位后，他能能飞到的高度区间为 [\max(0,H-T),H+T]。

但这个区间并不是全部合法。

比如说在 t_1 处，有高度限制的话，合法的区间应该是 [\max(0,H-t_1),H+t_1] \cap [l_1,u_1]。

那我们到设达第 i 个有高度限制的点时，高桥能飞到的合法高度区间为 [L_i,R_i] ， 显然有 [L_i,R_i]=[\max(L_{i-1}-(t_i-t_{i-1}),0),R_{i-1}+(t_i-t_{i-1})] \cap [l_i,u_i]。

初始时 L_0=R_0=H。

当 [L_i,R_i] 为空集时，没有合法方案。否则就有。

:::info[code]

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
long long sum[N];
long long t[N],u[N],d[N];
long long n,h,l,r;
void solve()
{
    cin>>n>>h;
    l=r=h;
    for(int i=1;i<=n;i++) cin>>t[i]>>d[i]>>u[i];
    for(int i=1;i<=n;i++)
    {
        long long minn=max(0ll,l-(t[i]-t[i-1]));
        long long maxn=r+(t[i]-t[i-1]);

        if(maxn>=d[i]&&minn<=u[i]&&maxn>=minn)
        {
            r=min(u[i],maxn);
            l=max(d[i],minn);//算出 [L_i,R_i]
        }
        else
        {
            cout<<"No\n";//为空集
            return;
        }
    }
    cout<<"Yes\n";
}
int T;
int main()
{
    cin>>T;
    while(T--) solve();
    return 0;
}

:::