結果
問題 | No.674 n連勤 |
ユーザー |
![]() |
提出日時 | 2024-06-05 15:37:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 1,903 bytes |
コンパイル時間 | 653 ms |
コンパイル使用メモリ | 77,712 KB |
最終ジャッジ日時 | 2025-02-21 19:26:39 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#line 1 "test/yukicoder/1601.test.cpp"#define PROBLEM "https://yukicoder.me/problems/1601"#include <iostream>#line 2 "datastructure/range_set.hpp"#include <map>template <typename T>struct range_set {public:range_set(bool merge_adjacent = true) : _merge_adjacent(merge_adjacent) {}typename std::map<T, T>::const_iterator get(T p) const {auto it = ranges.upper_bound(p);if (it == ranges.begin()) return ranges.end();if (std::prev(it)->second < p) return ranges.end();return it;}void insert(T l, T r) {insert(l, r, [](T, T) {}, [](T, T) {});}template <class op_insert, class op_erase>void insert(T l, T r, const op_insert &f, const op_erase &g) {auto it_l = ranges.upper_bound(l);auto it_r = ranges.upper_bound(r + T(_merge_adjacent));if (it_l != ranges.begin() &&l - T(_merge_adjacent) <= std::prev(it_l)->second) {it_l--;}for (auto it = it_l; it != it_r; it = ranges.erase(it)) {l = std::min(l, it->first);r = std::max(r, it->second);g(it->first, it->second);}ranges[l] = r;f(l, r);}typename std::map<T, T>::const_iterator begin() const {return ranges.begin();}typename std::map<T, T>::const_iterator end() const {return ranges.end();}private:std::map<T, T> ranges;bool _merge_adjacent;};#line 6 "test/yukicoder/1601.test.cpp"int main() {long long d;int q;std::cin >> d >> q;range_set<long long> st;long long ans = 0;while (q--) {long long a, b;std::cin >> a >> b;st.insert(a, b,[&](long long l, long long r) { ans = std::max(ans, r - l + 1); },[](long long, long long) {});std::cout << ans << '\n';}}