結果

問題 No.674 n連勤
コンテスト
ユーザー shogo314
提出日時 2025-01-15 18:22:52
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,923 bytes
コンパイル時間 1,411 ms
コンパイル使用メモリ 125,160 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-01-15 18:22:55
合計ジャッジ時間 2,803 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 10 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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() {
    int 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;
    }
}
0