結果
問題 | No.674 n連勤 |
ユーザー |
![]() |
提出日時 | 2023-01-19 16:56:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 79 ms / 2,000 ms |
コード長 | 5,718 bytes |
コンパイル時間 | 902 ms |
コンパイル使用メモリ | 89,716 KB |
最終ジャッジ日時 | 2025-02-10 04:12:04 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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_map.hpp"#include <algorithm>#include <cassert>#line 5 "datastructure/range_map.hpp"#include <map>#include <optional>#include <vector>template <typename T, typename U>struct range_map {public:range_map(bool merge_adjacent_segment = true): merge_adjacent_segment(merge_adjacent_segment) {}void clear() {mp.clear();}size_t size() {return mp.size();}std::optional<std::pair<T, T>> contains(T l, T r) {assert(l <= r);auto it = mp.upper_bound(l);if (it == mp.begin()) return std::nullopt;it--;if (it->first > l) return std::nullopt;if (r > it->second.first) return std::nullopt;return std::make_pair(it->first, it->second.first);}std::optional<std::pair<T, T>> contains(T p) {return is_covered(p, p);}void insert(T l, T r, U x) {assert(l <= r);auto it_l = mp.upper_bound(l);auto it_r = mp.upper_bound(r + int(merge_adjacent_segment));if (it_l != mp.begin()) {if (std::prev(it_l)->second.first >=l - int(merge_adjacent_segment)) {it_l--;}};bool has_value_0 = false, has_value_1 = false;T l_0, r_0, l_1, r_1, l_2, r_2;U x_0, x_1, x_2;if (it_l != mp.end()) {has_value_0 = true;l_0 = it_l->first;r_0 = it_l->second.first;x_0 = it_l->second.second;}{l_1 = l, r_1 = r;x_1 = x;}if (it_r != mp.begin()) {has_value_1 = true;l_2 = std::prev(it_r)->first;r_2 = std::prev(it_r)->second.first;x_2 = std::prev(it_r)->second.second;}for (auto it = it_l; it != it_r; it = mp.erase(it)) {}if (has_value_0 && x_0 == x_1) {l_1 = std::min(l_0, l_1);} else if (has_value_0 && l_0 < l_1) {mp[l_0] = {l_1 - 1, x_0};}if (has_value_1 && x_1 == x_2) {r_1 = std::max(r_1, r_2);} else if (has_value_1 && r_1 < r_2) {mp[r_1 + 1] = {r_2, x_2};}mp[l_1] = {r_1, x_1};}/* template <class op_erase, class op_insert>void insert(T l, T r, U x, const op_erase &f, const op_insert &g) {assert(l <= r);auto it_l = mp.upper_bound(l);auto it_r = mp.upper_bound(r + int(merge_adjacent_segment));if (it_l != mp.begin()) {if (std::prev(it_l)->second.first >=l - int(merge_adjacent_segment) &&std::prev(it_l)->second.second == x) {it_l--;}}for (auto it = it_l; it != it_r; it = mp.erase(it)) {f(it->first, it->second.first, it->second.second);l = std::min(l, it->first);r = std::max(r, it->second.first);}mp[l] = {r, x};g(l, r, x);}void erase(T l, T r) {assert(l <= r);auto it_l = mp.upper_bound(l);auto it_r = mp.upper_bound(r);if (it_l != mp.begin()) {if (std::prev(it_l)->second.first >= l) {it_l--;}}T nl = std::min(l, it_l->first);T nr = std::max(r, std::prev(it_r)->second.first);U nl_x = it_l->second.second;U nr_x = std::prev(it_r)->second.second;for (auto it = it_l; it != it_r; it = mp.erase(it)) {}if (nl < l) mp[nl] = {l - 1, nl_x};if (r < nr) mp[r + 1] = {nr, nr_x};}template <class op_erase, class op_insert>void erase(T l, T r, const op_erase &f, const op_insert &g) {assert(l <= r);auto it_l = mp.upper_bound(l);auto it_r = mp.upper_bound(r);if (it_l != mp.begin()) {if (std::prev(it_l)->second.first >= l) {it_l--;}}T nl = std::min(l, it_l->first);T nr = std::max(r, std::prev(it_r)->second.first);U nl_x = it_l->second.second;U nr_x = std::prev(it_r)->second.second;for (auto it = it_l; it != it_r; it = mp.erase(it)) {f(it->first, it->second.first, it->second.second);}if (nl < l) {mp[nl] = {l - 1, nl_x};g(nl, l - 1, nl_x);}if (r < nr) {mp[r + 1] = {nr, nr_x};g(r + 1, nr, nr_x);}} */private:bool merge_adjacent_segment;std::map<T, std::pair<T, U>> mp;};#line 3 "datastructure/range_set.hpp"template <typename T>struct range_set : range_map<T, bool> {using Base = range_map<T, bool>;using Base::range_map;void insert(T l, T r) {Base::insert(l, r, true);}template <class op_erase, class op_insert>void insert(T l, T r, const op_erase &f, const op_insert &g) {Base::insert(l, r, true, f, g);}};#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, bool x) {},[&](long long l, long long r, bool x) {ans = std::max(ans, r - l + 1);}); */st.insert(a, b);auto [l, r] = st.contains(a, b).value();ans = std::max(ans, r - l + 1);std::cout << ans << '\n';}}