#1023975 (C++23) No.674 n連勤

提出ソース

結果

問題	No.674 n連勤
ユーザー	Tatsu_mr
提出日時	2024-11-01 21:36:44
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	5,913 bytes
コンパイル時間	3,272 ms
コンパイル使用メモリ	252,632 KB
実行使用メモリ	13,636 KB
最終ジャッジ日時	2024-11-01 21:36:52
合計ジャッジ時間	8,145 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 13,636 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,820 KB
testcase_04	AC	2 ms 6,816 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	2 ms 6,820 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	2 ms 6,820 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	2 ms 6,816 KB
testcase_11	AC	8 ms 6,820 KB
testcase_12	AC	18 ms 6,816 KB
testcase_13	AC	72 ms 6,820 KB
testcase_14	AC	79 ms 6,816 KB
testcase_15	AC	72 ms 6,820 KB
testcase_16	TLE	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#define For(i, a, b) for(long long i = a; i < b; i++)
#define rep(i, n) For(i, 0, n)
#define rFor(i, a, b) for(long long i = a; i >= b; i--)
#define ALL(v) (v).begin(), (v).end()
#define rALL(v) (v).rbegin(), (v).rend()
using namespace std;

using lint = long long;
using ld = long double;

int INF = 2000000000;
lint LINF = 1000000000000000000;

template <class S, class T = int>
struct IntervalSet {
    public:
    struct Node {
        S l, r;
        T val;
        
        bool operator<(const Node &a) const {
            return (l != a.l ? l < a.l : r < a.r);
        }
    };
    
    IntervalSet() {
        s.insert({-SINF, -SINF, 0});
        s.insert({SINF, SINF, 0});
    }
    
    bool covered(S l, S r) {
        assert(l <= r);
        if (l == r) {
            return true;
        }
        auto it = prev(s.upper_bound({l, SINF, 0}));
        return (it->l <= l && r <= it->r);
    }
    
    bool covered(S x) {
        return covered(x, x + 1);
    }
    
    // [l, r) を含む区間 なければ [l, r) のすぐ左の区間
    auto get(S l, S r) {
        assert(l < r);
        return prev(s.upper_bound({l, SINF, 0}));
    }
    
    auto get(S x) {
        return get(x, x + 1);
    }
    
    template <class ADD, class DEL>
    void insert(S l, S r, T x, ADD add, DEL del) {
        assert(l <= r);
        if (l == r) {
            return;
        }
        auto it = prev(s.upper_bound({l, SINF, 0}));
        if (it->l <= l && r <= it->r) {
            S L = it->l, R = it->r;
            T X = it->val;
            if (x == X) {
                return;
            }
            del(L, R, X);
            s.erase(it);
            if (L < l) {
                add(L, l, X);
                s.insert({L, l, X});
            }
            if (r < R) {
                add(r, R, X);
                s.insert({r, R, X});
            }
            add(l, r, x);
            s.insert({l, r, x});
            return;
        }
        if (it->l <= l && l <= it->r) {
            S L = it->l, R = it->r;
            T X = it->val;
            del(L, R, X);
            it = s.erase(it);
            if (x == X) {
                l = L;
            } else {
                if (L < l) {
                    add(L, l, X);
                    s.insert({L, l, X});
                }
            }
        } else {
            it = next(it);
        }
        while (it->r <= r) {
            del(it->l, it->r, it->val);
            it = s.erase(it);
        }
        if (it->l <= r) {
            S L = it->l, R = it->r;
            T X = it->val;
            del(L, R, X);
            s.erase(it);
            if (x == X) {
                r = R;
            } else {
                if (r < R) {
                    add(r, R, X);
                    s.insert({r, R, X});
                }
            }
        }
        add(l, r, x);
        s.insert({l, r, x});
        return;
    }
    
    template <class ADD, class DEL>
    void insert(S l, S r, ADD add, DEL del) {
        insert(l, r, T(0), add, del);
    }
    
    void insert(S l, S r, T x = 0) {
        auto func = [](S l, S r, T x) {};
        insert(l, r, x, func, func);
    }
    
    void insert(S l) {
        auto func = [](S l, S r, T x) {};
        insert(l, l + 1, T(0), func, func);
    }
    
    template <class ADD, class DEL>
    void erase(S l, S r, ADD add, DEL del) {
        assert(l <= r);
        if (l == r) {
            return;
        }
        auto it = prev(s.upper_bound({l, SINF, 0}));
        if (it->l <= l && r <= it->r) {
            S L = it->l, R = it->r;
            T X = it->val;
            del(L, R, X);
            s.erase(it);
            if (L < l) {
                add(L, l, X);
                s.insert({L, l, X});
            }
            if (r < R) {
                add(r, R, X);
                s.insert({r, R, X});
            }
            return;
        }
        if (it->l <= l && l < it->r) {
            S L = it->l, R = it->r;
            T X = it->val;
            del(L, R, X);
            it = s.erase(it);
            if (L < l) {
                add(L, l, X);
                s.insert({L, l, X});
            }
        } else {
            it = next(it);
        }
        while (it->r <= r) {
            del(it->l, it->r, it->val);
            it = s.erase(it);
        }
        if (it->l < r) {
            S L = it->l, R = it->r;
            T X = it->val;
            del(L, R, X);
            s.erase(it);
            add(r, R, X);
            s.insert({r, R, X});
        }
        return;
    }
    
    void erase(S l, S r) {
        auto func = [](S l, S r, T x) {};
        erase(l, r, func, func);
    }
    
    void erase(S l) {
        auto func = [](S l, S r, T x) {};
        erase(l, l + 1, func, func);
    }
    
    int size() {
        return (int)s.size() - 2;
    }
    
    S mex(S x = 0) {
        auto it = prev(s.upper_bound({x, SINF, 0}));
        if (it->l <= x && x < it->r) {
            return it->r;
        } else {
            return x;
        }
    }
    
    set<Node> get_all() {
        return s;
    }
    
    void dump() {
        for (auto node : s) {
            if (abs(node.l) != SINF) {
                cout << "[" << node.l << ", " << node.r << "):" << node.val << " ";
            }
        }
        cout << endl;
    }
    
    private:
    set<Node> s;
    S SINF = numeric_limits<S>::max();
    T TINF = numeric_limits<T>::max();
};

int main() {
    lint d;
    int q;
    cin >> d >> q;
    IntervalSet<lint> s;
    while (q--) {
        lint a, b;
        cin >> a >> b;
        b++;
        s.insert(a, b);
        auto ss = s.get_all();
        lint ans = 0;
        for (auto n : ss) {
            if (abs(n.l) == numeric_limits<lint>::max()) {
                continue;
            }
            ans = max(ans, n.r - n.l);
        }
        cout << ans << endl;
    }
}

yukicoder

結果

テストケース

ソースコード