Codeforces 1463C Busy Robot

题意

给机器人$n$个操作，每个操作有一个$t_i$和一个$x_i$，意为在$t_i$时刻，会下令让机器人去往$x_i$。

机器人最初在$0$位置，其速度为每秒$1$单位，如果其在移动过程中被下令，它会忽视这个命令。

如果在$[t_i,t_{i+1}]$中任意时刻其到达了$x_i$，那么第$i$个命令视为有效的（注意$t_{n+1}=+\infty$），问有多少个有效的命令。

分析

看题就可以知道是一个模拟，假设机器人现在位置是$prex$，现在的时间是$pret$，那么对于第$i$号指令来说

如果$t\leq t_i$，那么它会执行这个指令，会在$pret+abs(x_i-x)$时刻到达$x_i$处，花费时间为$abs(x_i-x)$，且在$[pret,pret+abs(x_i-x)]$过程中，它会忽视这个指令，那么我们可以将当前时间$t$视为$pret+abs(x_i-x)$，其目的地为$x$。
如果$t>t_i$，那么它会忽视这个指令。

考虑统计答案

如果$t\leq t_i$，那么如果其到达了$x$还没有接到下一个命令，即$t_i+abs(x_i-x)\leq t_{i+1}$，那么该命令有效。
如果$t>t_i$，那么首先得保证$x_i$在$prex$到$x$的路上，其次注意到到达$x_i$的时间为$pret+abs(x_i-prex)$，按照题意，如果其时间在$[t_i,t_{i+1}]$间，那么该命令有效。

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define repd(z, x, y) for(int z=x;z>=y;--z)
#define com bool operator<(const node &b)const
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn = (ll) 1e6 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;
pii a[maxn];

void solve() {
    int n;
    cin >> n;
    rep(i, 1, n)cin >> a[i].first >> a[i].second;
    int x = 0, t = 0;
    int prex = 0, pret = 0;
    int num = 0;
    a[n + 1].first = LLONG_MAX;
    rep(i, 1, n) {
        if (t <= a[i].first) {
            prex = x;
            pret = a[i].first;
            t = a[i].first + abs(a[i].second - x);
            x = a[i].second;
            if (t <= a[i + 1].first)
                ++num;
        } else {
            int l = min(prex, x), r = max(prex, x);
            if (a[i].second >= l && a[i].second <= r) {
                int tim = pret + abs(a[i].second - prex);
                if (tim >= a[i].first && tim <= a[i + 1].first)
                    ++num;
            }
        }
    }
    cout << num << '\n';
}

signed main() {
    start;
    cin >> T;
    while (T--)
        solve();
    return 0;
}