結果
問題 | No.674 n連勤 |
ユーザー | suisen |
提出日時 | 2021-09-21 20:36:08 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 23 ms / 2,000 ms |
コード長 | 4,270 bytes |
コンパイル時間 | 842 ms |
コンパイル使用メモリ | 83,468 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-04 05:10:07 |
合計ジャッジ時間 | 2,024 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 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 | 1 ms
5,376 KB |
testcase_11 | AC | 3 ms
5,376 KB |
testcase_12 | AC | 3 ms
5,376 KB |
testcase_13 | AC | 13 ms
5,376 KB |
testcase_14 | AC | 14 ms
5,376 KB |
testcase_15 | AC | 13 ms
5,376 KB |
testcase_16 | AC | 23 ms
5,376 KB |
testcase_17 | AC | 23 ms
5,376 KB |
testcase_18 | AC | 20 ms
5,376 KB |
testcase_19 | AC | 14 ms
5,376 KB |
ソースコード
#define PROBLEM "https://yukicoder.me/problems/no/674" #include <iostream> #include <map> namespace suisen { template <typename T, bool merge_adjacent_segment = true> struct RangeSet : public std::map<T, T> { public: RangeSet() : _size(0) {} // returns the number of intergers in this set (not the number of ranges). O(1) T size() const { return number_of_elements(); } // returns the number of intergers in this set (not the number of ranges). O(1) T number_of_elements() const { return _size; } // returns the number of ranges in this set (not the number of integers). O(1) int number_of_ranges() const { return std::map<T, T>::size(); } // returns whether the given integer is in this set or not. O(log N) bool contains(T x) const { auto it = this->upper_bound(x); return it != this->begin() and x <= std::prev(it)->second; } /** * returns the iterator pointing to the range [l, r] in this set s.t. l <= x <= r. * if such a range does not exist, returns `end()`. * O(log N) */ auto find_range(T x) const { auto it = this->upper_bound(x); return it != this->begin() and x <= (--it)->second ? it : this->end(); } // returns whether `x` and `y` is in this set and in the same range. O(log N) bool in_the_same_range(T x, T y) const { auto it = get_containing_range(x); return it != this->end() and it->first <= y and y <= it->second; } // inserts the range [x, x] and returns the number of integers inserted to this set. O(log N) T insert(T x) { return insert(x, x); } // inserts the range [l, r] and returns the number of integers inserted to this set. amortized O(log N) T insert(T l, T r) { if (l > r) return 0; auto it = this->upper_bound(l); if (it != this->begin() and is_mergeable(std::prev(it)->second, l)) { it = std::prev(it); l = std::min(l, it->first); } T inserted = 0; for (; it != this->end() and is_mergeable(r, it->first); it = std::map<T, T>::erase(it)) { auto [cl, cr] = *it; r = std::max(r, cr); inserted -= cr - cl + 1; } inserted += r - l + 1; (*this)[l] = r; _size += inserted; return inserted; } // erases the range [x, x] and returns the number of intergers erased from this set. O(log N) T erase(T x) { return erase(x, x); } // erases the range [l, r] and returns the number of intergers erased from this set. amortized O(log N) T erase(T l, T r) { if (l > r) return 0; T tl = l, tr = r + 1; auto it = this->upper_bound(l); if (it != this->begin() and l <= std::prev(it)->second) { it = std::prev(it); tl = it->first; } T erased = 0; for (; it != this->end() and it->first <= r; it = std::map<T, T>::erase(it)) { auto [cl, cr] = *it; tr = cr; erased += cr - cl + 1; } if (tl < l) { (*this)[tl] = l - 1; erased -= l - tl; } if (r < tr) { (*this)[r + 1] = tr; erased -= tr - r; } _size -= erased; return erased; } private: T _size; bool is_mergeable(T cur_r, T next_l) { return next_l <= cur_r + merge_adjacent_segment; } }; } // namespace suisen using suisen::RangeSet; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); long long d; int q; std::cin >> d >> q; long long ans = 0; RangeSet<long long> set; while (q --> 0) { long long l, r; std::cin >> l >> r; set.insert(l, r); auto [nl, nr] = *set.find_range(l); ans = std::max(ans, nr - nl + 1); std::cout << ans << '\n'; } return 0; }