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

• 問題: No.674 n連勤
• ユーザー: mugen_1337
• 提出日時: 2024-04-29 12:04:45
• 言語: C++23(gcc13) (gcc 13.2.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 88 ms / 2,000 ms
• コード長: 5,272 bytes
• コンパイル時間: 1,350 ms
• コンパイル使用メモリ: 111,908 KB
• 実行使用メモリ: 6,820 KB
• 最終ジャッジ日時: 2024-11-18 15:12:09
• 合計ジャッジ時間: 3,224 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,820 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,820 KB
testcase_05	AC	2 ms; 6,816 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,820 KB
testcase_10	AC	2 ms; 6,820 KB
testcase_11	AC	8 ms; 6,820 KB
testcase_12	AC	8 ms; 6,816 KB
testcase_13	AC	71 ms; 6,820 KB
testcase_14	AC	76 ms; 6,820 KB
testcase_15	AC	70 ms; 6,820 KB
testcase_16	AC	88 ms; 6,816 KB
testcase_17	AC	88 ms; 6,820 KB
testcase_18	AC	75 ms; 6,816 KB
testcase_19	AC	72 ms; 6,816 KB

ソースコード

#line 1 "a.cpp"
#include <algorithm>
#include <iostream>

#line 1 "include/type.hpp"



// default types
using int8 = signed char;
using int32 = int;
using int64 = long long;

using float32 = float;
using float64 = double;

namespace MGN
{

}  // namespace MGN


#line 1 "include/data_structure/interval_set.hpp"



#include <concepts>
#line 6 "include/data_structure/interval_set.hpp"
#include <iterator>
#include <numeric>
#include <set>

#line 1 "include/assert.hpp"



#include <cstdlib>
#line 6 "include/assert.hpp"

#line 8 "include/assert.hpp"

namespace MGN
{

namespace _internal
{

void myError(
        const std::string& message,
        const std::string& func,
        const std::string& file,
        int32 line
)
{
        std::cerr << "MGN Error " << file << ":" << line << " in function " << func << std::endl;
        std::abort();
}

} // namespace

#define error(message) _internal::myError(message, __FUNCTION__, __FILE__, __LINE__);
#define assert(expr) if(!(expr)) { _internal::myError("Assertion \'" + std::string(#expr) + "\' failed.", __FUNCTION__, __FILE__, __LINE__); }

} // namespace MGN


#line 12 "include/data_structure/interval_set.hpp"

namespace MGN
{

enum IntervalType
{
        INTERVAL_TYPE_OPEN,
        INTERVAL_TYPE_CLOSE,
        INTERVAL_TYPE_LEFT_OPEN,
        INTERVAL_TYPE_RIGHT_OPEN
};

template <std::integral T>
struct Interval
{
public:
        T L, R;
        Interval() : L(T(0)), R(T(0)) {}
        Interval(T L_, T R_) : L(L_), R(R_)
        {
                assert(L_ <= R_);
        }
        Interval(T x) : L(x), R(x) {}

        bool cover(T x) const
        {
                return L <= x && x <= R;
        }

        bool cover(const Interval<T>& x) const
        {
                return L <= x.L && x.R <= R;
        }

        T count() const
        {
                return R - L + 1; 
        }
};

template <typename T>
bool operator<(const Interval<T>& lhs, const Interval<T>& rhs)
{
        if (lhs.L != rhs.L)
                return lhs.L < rhs.L;
        return lhs.R < rhs.R;
}

template <std::integral T>
class IntervalSet
{
public:

        // constructors / destructors
        IntervalSet() : _tMin(std::numeric_limits<T>::min()), _tMax(std::numeric_limits<T>::max())
        {
                _intervals.emplace(_tMin, _tMin);
                _intervals.emplace(_tMax, _tMax);
        }

        ~IntervalSet(){}

        // Does this set cover x ?
        bool cover(const Interval<T>& x) const
        {
                const auto ite = std::prev(_intervals.lower_bound(Interval(x.L + 1)));
                return ite->cover(x);
        }

        bool cover(T x) const
        {
                return cover(Interval(x, x));
        }

        // Return the amount of increase
        T addInterval(const Interval<T>& x)
        {
                auto ite = std::prev(_intervals.lower_bound(Interval(x.L + 1)));

                // nothing to do
                if (ite->cover(x))
                        return T(0);

                // iterating
                T sum(0);
                Interval<T> merged = x;
                auto eraseInterval = [&]()
                {
                        sum += ite->count();
                        ite = _intervals.erase(ite);
                };

                if (ite->cover(x.L) || ite->R + 1 == x.L)
                {
                        merged.L = ite->L;
                        ite = _intervals.erase(ite);
                }
                else
                {
                        ite = std::next(ite);
                }

                while (ite->R < merged.R)
                        eraseInterval();

                if (ite->cover(x.R)|| ite->L == x.R + 1)
                {
                        merged.R = ite->R;
                        eraseInterval();
                }

                _intervals.insert(merged);
                return merged.count() - sum;
        }

        T addInterval(T x)
        {
                return addInterval(Interval(x, x));
        }

        Interval<T> getCoveringInterval(T x) const
        {
                assert(cover(x));
                const auto ite = std::prev(_intervals.lower_bound(Interval(x + 1)));
                return *ite;
        }

        friend std::ostream& operator<<(std::ostream& os, const IntervalSet<T>& p)
        {
                for (const auto i : p._intervals)
                {
                        if (i.L == p._tMin || i.L == p._tMax)
                                continue;
                        os << "(" << i.L << ", " << i.R << ") ";
                }
                return os;
        }

private:
        T _tMin, _tMax;
        std::set<Interval<T>> _intervals;
};

}  // namespace MGN


#line 6 "a.cpp"

int main()
{
        int64 D;
        int32 Q;
        std::cin >> D >> Q;

        int64 answer = 0;
        MGN::IntervalSet<int64> intervals;
        for (int i = 0; i < Q; i++)
        {
                int64 a, b;
                std::cin >> a >> b;

                intervals.addInterval(MGN::Interval(a, b));
                const auto cur = intervals.getCoveringInterval(a);
                answer = std::max(cur.count(), answer);
                std::cout << answer << "\n";
        }
        return 0;
}