#932088 (C++17) No.674 n連勤

• 問題: No.674 n連勤
• ユーザー: idat_50me
• 提出日時: 2023-11-27 15:11:23
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 98 ms / 2,000 ms
• コード長: 1,865 bytes
• コンパイル時間: 2,011 ms
• コンパイル使用メモリ: 201,608 KB
• 最終ジャッジ日時: 2025-02-18 01:58:03
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 17

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T> struct SegmentSet {
private:
    map<T, T> mp;
public:
    SegmentSet() : mp(){};
    void insert(T x) {
        insert(x, x);
    }
    void insert(T l, T r) {
        assert(l <= r);
        auto itr_l = mp.upper_bound(l), itr_r = mp.upper_bound(r + 1);
        if(itr_l != mp.begin()) {
            if((--itr_l)->second < l - 1) itr_l++;
        }
        if(itr_l != itr_r) {
            l = std::min(l, itr_l->first);
            r = std::max(r, prev(itr_r)->second);
            mp.erase(itr_l, itr_r);
        }
        mp[l] = r;
    }
    void erase(T x) {
        erase(x, x);
    }
    void erase(T l, T r) {
        assert(l <= r);
        auto itr_l = mp.upper_bound(l), itr_r = mp.upper_bound(r);
        if(itr_l != mp.begin()) {
            if((--itr_l)->second < l) itr_l++;
        }
        if(itr_l == itr_r) return;
        T tmp_l = itr_l->first, tmp_r = prev(itr_r)->second;
        mp.erase(itr_l, itr_r);
        if(tmp_l < l) mp[tmp_l] = l - 1;
        if(r < tmp_r) mp[r + 1] = tmp_r;
    }
    pair<T, T> get_seg(T x) {
        auto itr = mp.upper_bound(x);
        if(itr == mp.begin() or (--itr)->second < x) return pair<T, T>(0, -1);
        return pair<T, T>(itr->first, itr->second);
    }
    T min() {
        return mp.begin()->first;
    }
    T max() {
        return mp.rbegin()->second;
    }
    T mex(T x = 0) {
        pair<T, T> p = get_seg(x);
        if(p.first > p.second) return x;
        return p.second + 1;
    }
    bool same(T x, T y) {
        pair<T, T> p = get_seg(x);
        return p.first <= p.second and p.first <= y and y <= p.second;
    }
    int size() {
        return int(mp.size());
    }
    void out() {
        for(auto [l, r] : mp) cout << "[" << l << ", " << r << "]\n";
    }
};
int main() {
    long long D;
    int Q;
    SegmentSet<long long> s;
    cin >> D >> Q;
    long long ans = 0;
    for(int i = 0; i < Q; i++) {
        long long A, B;
        cin >> A >> B;
        s.insert(A, B);
        auto p = s.get_seg(A);
        ans = max(ans, p.second - p.first + 1);
        cout << ans << endl;
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX