結果

問題 No.674 n連勤
ユーザー mugen_1337
提出日時 2024-04-29 12:04:45
言語 C++23
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0