結果

問題 No.674 n連勤
コンテスト
ユーザー Jikky1618
提出日時 2024-12-22 20:51:57
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 32 ms / 2,000 ms
コード長 2,509 bytes
コンパイル時間 2,233 ms
コンパイル使用メモリ 203,204 KB
最終ジャッジ日時 2025-02-26 16:08:11
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...)
#endif

template <class S, class T>
struct Intervals {
    static constexpr S INF = numeric_limits<S>::max() / 4;
    static constexpr S L = -INF, R = INF;
    // data[l] : 区間 [l, r) に割り当てられた値（r は次の区間の l）
    map<S, T> data;

    // 定義域を [L, R) とし，[L, R) = none_val で初期化
    Intervals(T none_val = -1) {
        data[L] = none_val;
        data[R] = none_val;
    }

    // [l, r) = v
    void set(S l, S r, T v = 1) {
        l = max(l, L), r = min(r, R);
        if (l >= r) return;
        auto it = data.upper_bound(l);
        auto pit = prev(it);
        T vR = pit->second;
        if (pit->first == l) {
            pit = data.erase(pit);
            pit = prev(pit);
        }
        T vL = pit->second;
        // 丸ごと上書きされる区間は削除
        while (it != data.end()) {
            if (it->first > r) break;
            vR = it->second;
            it = data.erase(it);
        }
        if (v != vR) data[r] = vR;
        if (v != vL) data[l] = v;
    }

    // a[i]
    T get_value(S i) {
        assert(L <= i && i < R);
        return prev(data.upper_bound(i))->second;
    }

    // i を含む値の等しい極大区間が [l, r) = v としたとき {l, r, v} を返す
    tuple<S, S, T> get(S i) {
        assert(L <= i && i < R);
        auto it = data.upper_bound(i);
        auto pit = prev(it);
        return {pit->first, it->first, pit->second};
    }

    // [l, r) を連長圧縮した結果を {左端, 右端, 値} のリストとして返す
    vector<tuple<S, S, T>> get_all(S l, S r) {
        l = max(l, L), r = min(r, R);
        if (l >= r) return vector<tuple<S, S, T>>();
        vector<tuple<S, S, T>> res;
        auto nit = data.upper_bound(l), it = prev(nit);
        T i = it->first;
        while (i < r) {
            T ni = nit->first;
            res.emplace_back(max(i, l), min(ni, r), it->second);
            i = ni;
            it = nit++;
        }
        return res;
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    ll D, Q;
    cin >> D >> Q;

    ll ans = 0;
    Intervals<ll, ll> I;
    while (Q--) {
        ll A, B;
        cin >> A >> B;
        I.set(A, B + 1);
        auto [l, r, v] = I.get(A);
        ans = max(ans, r - l);
        cout << ans << '\n';
    }
}
0