結果
| 問題 | No.674 n連勤 |
| ユーザー |
 shogo314
|
| 提出日時 | 2025-01-15 18:25:41 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 151 ms / 2,000 ms |
| コード長 | 6,922 bytes |
| コンパイル時間 | 1,339 ms |
| コンパイル使用メモリ | 125,228 KB |
| 実行使用メモリ | 13,532 KB |
| 最終ジャッジ日時 | 2025-01-15 18:25:46 |
| 合計ジャッジ時間 | 3,516 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
ソースコード
#line 1 "main.cpp"
#include <iostream>
#include <set>
#line 2 "monoid-unionfind.hpp"
/**
* @file monoid-unionfind.hpp
* @brief 可換モノイドを乗せるUnionFind
*/
#line 2 "unionfind.hpp"
/**
* @file unionfind.hpp
* @brief UnionFind
*/
#include <algorithm>
#include <cassert>
#include <vector>
/**
* @brief 無向グラフに対して「辺の追加」、「2頂点が連結かの判定」をする
*/
struct UnionFind {
protected:
int _n;
// 負ならサイズ、非負なら親
std::vector<int> parent_or_size;
public:
UnionFind() : _n(0) {}
explicit UnionFind(int n) : _n(n), parent_or_size(n, -1) {}
/**
* @brief 辺(a,b)を足す
* @return 連結したものの代表元
*/
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
/**
* @brief 頂点a,bが連結かどうか
*/
bool same(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
/**
* @brief 頂点aの属する連結成分の代表元
*/
int leader(int a) {
assert(0 <= a && a < _n);
if (parent_or_size[a] < 0) return a;
int x = a;
while (parent_or_size[x] >= 0) {
x = parent_or_size[x];
}
while (parent_or_size[a] >= 0) {
int t = parent_or_size[a];
parent_or_size[a] = x;
a = t;
}
return x;
}
/**
* @brief 頂点aの属する連結成分のサイズ
*/
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
/**
* @brief グラフを連結成分に分け、その情報を返す
* @return 「一つの連結成分の頂点番号のリスト」のリスト
*/
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int>& v) { return v.empty(); }),
result.end());
return result;
}
};
#line 9 "monoid-unionfind.hpp"
/**
* @brief 可換モノイドを乗せるUnionFind
*
* @tparam S
* @tparam Op
*/
template <typename S, class Op>
class MonoidUnionFind : private UnionFind {
private:
std::vector<S> val;
using UnionFind::_n;
using UnionFind::parent_or_size;
public:
inline constexpr static auto op = Op();
explicit MonoidUnionFind(std::vector<S> v) : UnionFind(v.size()), val(v) {}
MonoidUnionFind(int n, S e) : UnionFind(n), val(n, e) {}
using UnionFind::groups;
using UnionFind::leader;
using UnionFind::same;
using UnionFind::size;
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
val[x] = op(val[x], val[y]);
return x;
}
const S& prod(int a) {
return val[leader(a)];
}
};
#line 2 "more_functional.hpp"
/**
* @file more_functional.hpp
* @brief 関数オブジェクトを定義する
*/
#include <limits>
#include <numeric>
#include <type_traits>
#include <utility>
namespace more_functional {
template <typename S>
struct Max {
const S operator()(const S& a, const S& b) const { return std::max(a, b); }
};
template <typename S>
struct Min {
const S operator()(const S& a, const S& b) const { return std::min(a, b); }
};
template <typename S>
struct MinMax {
const std::pair<S, S> operator()(const std::pair<S, S>& a, const std::pair<S, S>& b) const { return {std::min(a.first, b.first), std::max(a.second, b.second)}; }
};
template <typename S, std::enable_if_t<std::is_integral_v<S>>* = nullptr>
struct Gcd {
constexpr S operator()(const S& a, const S& b) const { return std::gcd(a, b); }
};
template <typename S>
struct Zero {
S operator()() const { return S(0); }
};
template <typename S>
struct One {
S operator()() const { return S(1); }
};
template <typename S>
struct None {
S operator()() const { return S{}; }
};
template <typename S, std::enable_if_t<std::is_scalar_v<S>>* = nullptr>
struct MaxLimit {
constexpr S operator()() const { return std::numeric_limits<S>::max(); }
};
template <typename S, std::enable_if_t<std::is_scalar_v<S>>* = nullptr>
struct MinLimit {
constexpr S operator()() const { return std::numeric_limits<S>::lowest(); }
};
template <typename S, std::enable_if_t<std::is_scalar_v<S>>* = nullptr>
struct MaxMinLimit {
constexpr std::pair<S, S> operator()() const { return {std::numeric_limits<S>::max(), std::numeric_limits<S>::lowest()}; }
};
template <typename S>
struct Div {
S operator()(const S& a) const { return S(1) / a; }
};
} // namespace more_functional
#line 6 "main.cpp"
using ll = long long;
int main() {
ll D, Q;
std::cin >> D >> Q;
std::vector<std::pair<ll, ll>> AB(Q);
std::set<ll> s;
for (auto& [A, B] : AB) {
std::cin >> A >> B;
s.insert(A);
s.insert(A - 1);
s.insert(B);
s.insert(B + 1);
}
std::vector<ll> v(s.begin(), s.end());
std::vector<bool> f(s.size());
std::vector<std::pair<int, int>> init;
for (std::size_t i = 0; i < v.size(); i++) {
init.push_back({i, i});
}
MonoidUnionFind<std::pair<int, int>, more_functional::MinMax<int>> uf(init);
ll ans = 0;
for (auto [A, B] : AB) {
int k = std::lower_bound(v.begin(), v.end(), A) - v.begin();
std::pair<int, int> p = uf.prod(k);
while (v[p.second + 1] <= B) {
uf.merge(k, p.second + 1);
k = p.second + 1;
p = uf.prod(k);
}
if (f[p.first - 1]) {
uf.merge(p.first - 1, p.first);
}
if (f[p.second + 1]) {
uf.merge(p.second, p.second + 1);
}
f[p.first] = true;
f[p.second] = true;
p = uf.prod(k);
if (ans < v[p.second] - v[p.first] + 1) {
ans = v[p.second] - v[p.first] + 1;
}
std::cout << ans << std::endl;
}
}