結果
問題 | No.674 n連勤 |
ユーザー | mugen_1337 |
提出日時 | 2024-04-29 12:04:45 |
言語 | C++23(gcc13) (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 5,272 bytes |
コンパイル時間 | 3,369 ms |
コンパイル使用メモリ | 109,668 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-04-29 12:04:51 |
合計ジャッジ時間 | 5,315 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 1 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 1 ms
6,944 KB |
testcase_11 | AC | 7 ms
6,940 KB |
testcase_12 | AC | 7 ms
6,940 KB |
testcase_13 | AC | 71 ms
6,944 KB |
testcase_14 | AC | 75 ms
6,940 KB |
testcase_15 | AC | 70 ms
6,944 KB |
testcase_16 | AC | 87 ms
6,944 KB |
testcase_17 | AC | 92 ms
6,944 KB |
testcase_18 | AC | 78 ms
6,940 KB |
testcase_19 | AC | 76 ms
6,940 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; }