結果

問題 No.674 n連勤
コンテスト
ユーザー Demystify
提出日時 2022-07-03 22:57:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 28 ms / 2,000 ms
コード長 6,745 bytes
コンパイル時間 2,393 ms
コンパイル使用メモリ 202,960 KB
最終ジャッジ日時 2025-01-30 04:19:50
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// --------------------------------------------------------
#define FOR(i,l,r) for (ll i = (l); i < (r); ++i)
#define REP(i,n) FOR(i,0,n)
// --------------------------------------------------------

// References:
//   <https://satanic0258.github.io/snippets/data-structure/SegmentMap.html>
//   <https://rsk0315.hatenablog.com/entry/2020/10/11/125049>


// 区間を set で管理するデータ構造
//   - 区間 [l, m], [m + 1, r] をマージする場合、merge_adjacent を true にする
template<class T = ll>
struct range_set {
  public:
    range_set(bool merge_adjacent) : merge_adjacent(merge_adjacent) {
        T MN = numeric_limits<T>::min();
        T MX = numeric_limits<T>::max();
        mp.emplace(MN, MN);
        mp.emplace(MX, MX);
    }

    // x を含む区間 [l, r] を返す
    //   - O(log |S|)
    //   - contains(x) が true であることを想定
    pair<T, T> get(T x) const {
        auto it = prev(mp.upper_bound(x));
        auto [l, r] = *it;
        return make_pair(l, r);
    }

    // r < x を満たす区間 [l, r] のうち最右の区間を返す
    //   - O(log |S|)
    pair<T, T> get_left(T x) const {
        auto it = prev(mp.upper_bound(x));
        if (x <= it->second) { it--; }
        auto [l, r] = *it;
        return make_pair(l, r);
    }

    // x < l を満たす区間 [l, r] のうち最左の区間を返す
    //   - O(log |S|)
    pair<T, T> get_right(T x) const {
        auto it = mp.lower_bound(x + 1);
        auto [l, r] = *it;
        return make_pair(l, r);
    }

    // 区間 [x, x] を追加し、この区間と重なる区間を全てマージする
    //   - amortized O(log |S|)
    void insert(T x) { return insert(x, x); }

    // 区間 [l, r] を追加し、この区間と重なる区間を全てマージする
    //   - amortized O(log |S|)
    void insert(T l, T r) {
        assert(l <= r);
        auto it_L = prev(mp.upper_bound(l));
        auto it_R = mp.upper_bound(r + merge_adjacent);
        if (it_L->second + merge_adjacent < l) { it_L++; }
        if (it_L != it_R) {
            l = min(l, it_L->first);
            r = max(r, prev(it_R)->second);
            mp.erase(it_L, it_R);  // 区間 [l, r] と重なる区間を全削除
        }
        mp.emplace(l, r);
    }

    // 区間 [x, x] と重なる区間を全て削除する
    //   - amortized O(log |S|)
    bool erase(T x) { return erase(x, x); }

    // 区間 [l, r] と重なる区間を全て削除する
    //   - amortized O(log |S|)
    bool erase(T l, T r) {
        assert(l <= r);
        auto it_L = prev(mp.upper_bound(l));
        auto it_R = mp.upper_bound(r);
        if (it_L->second < l) { it_L++; }
        if (it_L == it_R) { return false; }

        T l2 = it_L->first;
        T r2 = prev(it_R)->second;
        mp.erase(it_L, it_R);  // 区間 [l, r] と重なる区間を全削除
        if (l2 < l) { mp.emplace(l2, l - 1); }
        if (r < r2) { mp.emplace(r + 1, r2); }

        return true;
    }

    // x を含む区間が存在するか判定する
    //   - O(log |S|)
    bool contains(T x) const {
        auto it = prev(mp.upper_bound(x));
        auto r = it->second;
        return x <= r;
    }

    // x, y が同じ区間に属しているか判定する
    // 一方が区間にすら属していない場合は false を返す
    //   - O(log |S|)
    bool same(T x, T y) const {
        auto it = prev(mp.upper_bound(x));
        auto [l, r] = *it;
        if (r < x) { return false; }
        return l <= y && y <= r;
    }

    // x 以上の値の範囲における mex を求める
    //   - O(log |S|)
    T mex(T x = 0) const {
        auto it = prev(mp.upper_bound(x));
        auto [l, r] = *it;
        return (l <= x && x <= r) ? r + 1 : x;
    }

    // 存在する区間の個数
    //   - O(1)
    int size() const noexcept { return mp.size(); }

  private:
    bool merge_adjacent;
    map<T, T> mp;
};


#if 0
// O(log(N) log(w))  w = 31
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int N, Q; cin >> N >> Q;

    int B = 31;
    vector<range_set<int>> rs_array(B, range_set<int>(false));

    // [l, r]
    auto update = [&](int l, int r, int x) -> void {
        REP(b,B) {
            auto& rs = rs_array[b];
            if ((x >> b) & 1) {
                rs.insert(l, r);
            } else {
                rs.erase(l, r);
            }
        }
    };
    auto query = [&](int i) -> int {
        int res = 0;
        REP(b,B) {
            auto& rs = rs_array[b];
            if (rs.contains(i)) {
                res += (1 << b);
            }
        }
        return res;
    };

    update(0, N-1, (1ll << 31) - 1);

    while (Q--) {
        int q; cin >> q;
        if (q == 0) {
            int s, t, x; cin >> s >> t >> x;
            update(s, t, x);
        } else {
            int i; cin >> i;
            int ans = query(i);
            cout << ans << '\n';
        }
    }

    return 0;
}
// Verify: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_D&lang=ja
# endif


#if 0
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int N; cin >> N;
    range_set<int> rs(true);
    REP(_,N) {
        int p; cin >> p;
        rs.insert(p);
        cout << rs.mex() << '\n';
    }

    return 0;
}
// Verify: https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_c
# endif


#if 0
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int N; cin >> N;

    range_set<ll> rs(true);

    REP(_,N) {
        ll S, C; cin >> S >> C;
        
        // 一つ目の白マスに移動
        ll x = rs.mex(S);

        while (true) {
            auto [l, r] = rs.get_right(x);
            if (x + C - 1 < l) {
                cout << x + C - 1 << '\n';
                rs.insert(x, x + C - 1);
                break;
            } else {
                rs.insert(x, l - 1);
                C -= l - x;
                x = r + 1;
            }
        }
    }

    return 0;
}
// Verify: https://atcoder.jp/contests/code-festival-2015-qualb/tasks/codefestival_2015_qualB_d
# endif


#if 1
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    ll D, Q; cin >> D >> Q;

    range_set<ll> rs(true);

    ll ans = 0;
    while (Q--) {
        ll A, B; cin >> A >> B;

        rs.insert(A, B);
        auto [l, r] = rs.get(A);
        ans = max(ans, r - l + 1);
        cout << ans << '\n';
    }

    return 0;
}
// Verify: https://yukicoder.me/problems/no/674
#endif
0