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

• 問題: No.674 n連勤
• ユーザー: sten_san
• 提出日時: 2022-02-01 17:33:07
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 63 ms / 2,000 ms
• コード長: 6,229 bytes
• コンパイル時間: 2,272 ms
• コンパイル使用メモリ: 206,592 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-11 09:11:09
• 合計ジャッジ時間: 3,618 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	7 ms; 5,376 KB
testcase_12	AC	7 ms; 5,376 KB
testcase_13	AC	51 ms; 5,376 KB
testcase_14	AC	52 ms; 5,376 KB
testcase_15	AC	49 ms; 5,376 KB
testcase_16	AC	63 ms; 5,376 KB
testcase_17	AC	63 ms; 5,376 KB
testcase_18	AC	59 ms; 5,376 KB
testcase_19	AC	50 ms; 5,376 KB

ソースコード

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

struct iofast_t {
    iofast_t() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} iofast;

struct uns_t {} uns;
template <typename Element, typename Head, typename ...Args>
auto vec(Element init, Head arg, Args ...args) {
    if constexpr (sizeof...(Args) == 0) return vector(arg, init);
    else return vector(arg, vec(init, args...));
}
template <typename Element, typename Head, typename ...Args>
auto vec(uns_t, Head arg, Args ...args) {
    return vec(Element(), arg, args...);
}

template <typename Container>
auto distance(const Container &c, decltype(begin(c)) iter) {
    return distance(begin(c), iter);
}

template <typename RIter, typename Compare = less<typename iterator_traits<RIter>::value_type>>
auto isort(RIter first, RIter last, Compare comp = Compare()) {
    vector<int> i(distance(first, last));
    iota(begin(i), end(i), 0);
    sort(begin(i), end(i), [&](auto x, auto y) {
        return comp(*(first + x), *(first + y));
    });
    return i;
}

template <typename, template <typename> typename, typename = void_t<>>
struct detect : false_type {};
template <typename T, template <typename> typename Check>
struct detect<T, Check, void_t<Check<T>>> : true_type {};
template <typename T, template <typename> typename Check>
constexpr inline bool detect_v = detect<T, Check>::value;

template <typename T>
using has_member_sort = decltype(declval<T>().sort());

template <typename Container, typename Compare = less<typename Container::value_type>>
auto sorted(Container c, Compare comp = Compare()) {
    if constexpr (detect_v<Container, has_member_sort>) {
        c.sort(comp);
        return c;
    }
    else {
        sort(begin(c), end(c), comp);
        return c;
    }
}

template <typename Container, typename Compare = equal_to<typename Container::value_type>>
auto uniqued(Container c, Compare comp = Compare()) {
    c.erase(unique(begin(c), end(c), comp), end(c));
    return c;
}

template <typename T, typename Compare = less<T>>
T &chmin(T &l, T r, Compare &&f = less<T>()) { return l = min(l, r, f); }
template <typename T, typename Compare = less<T>>
T &chmax(T &l, T r, Compare &&f = less<T>()) { return l = max(l, r, f); }

#ifndef STCP_SEGMENT_SET_HPP
#define STCP_SEGMENT_SET_HPP

#include <map>

#ifndef STCP_BASE_HPP
#define STCP_BASE_HPP

#include <utility>
#include <algorithm>
#include <numeric>
#include <iterator>

#include <optional>

#include <limits>
#include <cstdint>
#include <cstddef>

namespace stcp {
    using std::size_t;
    using std::int8_t;
    using std::uint8_t;
    using std::int16_t;
    using std::uint16_t;
    using std::int32_t;
    using std::uint32_t;
    using std::int64_t;
    using std::uint64_t;

    using std::pair;
    using std::optional;
    using std::nullopt;
    using std::make_pair;

    template <typename T>
    const inline auto inf = std::numeric_limits<T>::max();

    template <typename T>
    T &chmin(T &l, const T &r) {
        return l = std::min(l, r);
    }
    template <typename T, typename Compare>
    T &chmin(T &l, const T &r, Compare c) {
        return l = std::min(l, r, std::move(c));
    }

    template <typename T>
    T &chmax(T &l, const T &r) {
        return l = std::max(l, r);
    }
    template <typename T, typename Compare>
    T &chmax(T &l, const T &r, Compare c) {
        return l = std::max(l, r, std::move(c));
    }
}

#ifdef STCP_ENABLE_MULTIPRECISION

#include <boost/multiprecision/cpp_int.hpp>

namespace stcp {
    using bint = boost::multiprecision::cpp_int;

    template <>
    const inline bint inf<bint> = (bint(1) << 1023) - 1;
}

#endif // STCP_ENABLE_MULTIPRECISION

#endif // STCP_BASE_HPP

namespace stcp {
    template <typename Int = int64_t>
    struct segment_set {
        using int_type = Int;

        segment_set(): seg_() {
        }

    public:
        int_type insert(int_type l, int_type r, const bool connect_adjacent_segment = false) {
            if (r <= l) {
                return 0;
            }

            auto iter1 = seg_.upper_bound(l);
            auto iter2 = seg_.lower_bound(r + connect_adjacent_segment);

            if (iter1 != std::begin(seg_)) {
                std::advance(iter1, -1);
                if (l < iter1->second + connect_adjacent_segment) {
                    l = iter1->first;
                }
                std::advance(iter1, +1);
            }

            if (iter2 != std::begin(seg_)) {
                std::advance(iter2, -1);
                if (r <= iter2->second) {
                    r = iter2->second;
                }
                std::advance(iter2, +1);
            }

            seg_.erase(iter1, iter2);

            seg_[l] = r;

            return r - l;
        }

        void remove_covered(int_type l, int_type r) {
            if (r <= l) {
                return;
            }

            auto iter = seg_.upper_bound(l);

            if (iter != std::begin(seg_)) {
                std::advance(iter, -1);
            }

            while (iter->first < r) {
                if (l < iter->second) {
                    iter = seg_.erase(iter);
                }
                else {
                    std::advance(iter, +1);
                }
            }
        }

        void remove_covered(int_type x) {
            remove_covered(x, x + 1);
        }

        pair<int_type, int_type> covered(int_type x) const {
            auto iter = seg_.upper_bound(x);

            if (iter == std::begin(seg_)) {
                return { 0, 0 };
            }
            std::advance(iter, -1);

            if (iter->second <= x) {
                return { 0, 0 };
            }

            return *iter;
        }

        bool same(int_type x, int_type y) const {
            auto [l, r] = covered(x);
            return l <= y && y < r;
        }

    private:
        std::map<int_type, int_type> seg_;
    };
}

#endif // STCP_SEGMENT_SET_HPP

int main() {
    int64_t d; cin >> d;

    stcp::segment_set<int64_t> seg;

    int64_t max = 0;

    int q; cin >> q;
    while (q--) {
        int64_t a, b; cin >> a >> b; ++b;

        chmax(max, seg.insert(a, b, true));

        cout << max << endl;
    }
}