Competitive Programming Solutions

1463C - Busy Robot

17 Dec 2020 — Tags: implementation — URL

Compute the position $y_i$ of the robot at time $t_i$. Then, check if for each $i$, $x_i$ lies in the range $y_i, y_{i + 1}$.

Time complexity: $O(n)$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
int solve(vector<pll> tx)
{
    tx.emplace_back(1e13, 0);
    int ans = 0, n = (int)(tx).size();
    ll ts, xs, xe, te;
    ts = xs = xe = te = 0;
    vector<ll> y(n);
    for (int i = 0; i < n; ++i)
    {
        auto [ti, xi] = tx[i];
        y[i] = xs + (xe == xs ? 0 : (xe > xs ? 1 : -1)) * (min(ti, te) - ts);
        if (te <= ti)
        {
            ts = ti;
            xs = xe;
            te = ts + abs(xi - xs);
            xe = xi;
        }
    }
    auto inside = [](ll x, ll l, ll r) -> bool {
        if (l > r)
            swap(l, r);
        return l <= x and x <= r;
    };
    for (int i = 0; i < n - 1; ++i)
        ans += inside(tx[i].second, y[i], y[i + 1]);
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<pll> tx(n);
        for (auto &[t, x] : tx)
            cin >> t >> x;
        cout << solve(tx) << endl;
    }
    return 0;
}

Related posts