C. Air Conditioner (Codeforces Round #620 Div. 2)

問題

https://codeforces.com/contest/1304/problem/C

問題概要

n人のお客様があなたの店を訪れます。お客様は入店時の店の室温が一定の範囲でないと入店してくれません。また、この範囲はお客様ごとに異なります。お客様が来店する時間もまちまちです。

ところで、あなたの店の室温今m度です。また、1分で室温を1度上下させることが可能です。この条件ですべてのお客様を入店させることは可能ですか？

考察

愚直に、許容される温度の幅を記録しつつ、一人ずつお客様を迎えればいいだけです。

現在の室温の取りうる下限から次のお客様が来るまでにそのお客様の許容する上限にできない場合か、現在の室温の取りうる上限から次のお客様が来るまでにそのお客様の許容する下限にできない場合は"NO"になります。

なお、同時刻に複数のお客様が来ることがありますが、これは特に意識することなく、時間の差分を0として処理してしまえばよいです。

コンテストでは日和ってえぐいif文を並べてしまいました。→Submission #71152976 - Codeforces

今冷静に実装すると、"NO"になる条件のチェックと、上限加減の算出だけで済んでコンパクトになりました↓。本番でも冷静になってちゃんと設計を詰めたほうが成績は安定するんでしょうけど、なかなか・・・。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000001;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n, m;
        cin >> n >> m;
        vector<int> t(n);
        vector<int> l(n);
        vector<int> h(n);
        for (int i = 0; i < n; i++) cin >> t[i] >> l[i] >> h[i];
        int prev_t = 0;
        int lim_l = m;
        int lim_h = m;
        bool ok = true;
        for (int i = 0; i < n; i++) {
            int dt = t[i] - prev_t;
            if (lim_l - dt > h[i] || lim_h + dt < l[i]) {
                ok = false;
                break;
            }
            lim_l = max(l[i], lim_l - dt);
            lim_h = min(h[i], lim_h + dt);
            prev_t = t[i];
        }
        cout << (ok ? "YES" : "NO") << endl;
    }
}