結果

問題 No.674 n連勤
コンテスト
ユーザー Today03
提出日時 2024-10-22 09:58:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 94 ms / 2,000 ms
コード長 2,398 bytes
コンパイル時間 3,507 ms
コンパイル使用メモリ 251,864 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-22 09:59:04
合計ジャッジ時間 6,067 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9 + 10;
const ll INFL = 4e18;

struct RangeSet {
    set<pair<ll, ll>> dat;
    RangeSet() {
        dat.insert({-INFL, -INFL});
        dat.insert({INFL, INFL});
    }
    // RangeSet に区間 [l,r) を追加する。
    void insert(ll l, ll r) {
        assert(l < r);
        auto it = dat.lower_bound({l, 0});
        if (it != dat.begin()) {
            it--;
            if (it->second >= l) {
                l = it->first;
                r = max(r, it->second);
                it = dat.erase(it);
            } else {
                it++;
            }
        }
        while (it != dat.end() && it->first <= r) {
            r = max(r, it->second);
            it = dat.erase(it);
        }
        dat.insert({l, r});
    }
    // RangeSet から区間 [l,r) を削除する。
    void erase(ll l, ll r) {
        assert(l < r);
        auto it = dat.lower_bound({l, 0});
        if (it != dat.begin()) {
            it--;
            if (it->second > l) {
                ll L = it->first, R = it->second;
                it = dat.erase(it);
                if (L < l) dat.insert({L, l});
                if (r < R) dat.insert({r, R});
            } else {
                it++;
            }
        }
        while (it != dat.end() && it->first < r) {
            ll L = it->first, R = it->second;
            it = dat.erase(it);
            if (L < l) dat.insert({L, l});
            if (r < R) dat.insert({r, R});
        }
    }
    // 区間 [l,r) が RangeSet に完全に被覆されているかどうかを判定する。
    bool is_covered(ll l, ll r) {
        auto it = dat.upper_bound({l, INFL});
        if (it == dat.begin()) return false;
        it--;
        return it->first <= l && r <= it->second;
    }
    // 点 x を含む区間を返す。存在しない場合は {-INFL,-INFL} を返す。
    pair<ll, ll> covering_range(ll x) {
        if (!is_covered(x, x + 1)) return {-INFL, -INFL};
        auto it = dat.upper_bound({x, INFL});
        it--;
        return *it;
    }
};

int main() {
    ll D;
    int Q;
    cin >> D >> Q;

    ll ans = 0;
    RangeSet rs;
    while (Q--) {
        ll a, b;
        cin >> a >> b;

        rs.insert(a, b + 1);

        auto [l, r] = rs.covering_range(a);
        ans = max(ans, r - l);

        cout << ans << '\n';
    }
}
0