結果

問題 No.674 n連勤
ユーザー gyouzasushi
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

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