#828297 (C++17) No.674 n連勤

• 問題: No.674 n連勤
• ユーザー: suisen
• 提出日時: 2022-12-25 01:34:52
• 言語: C++17 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 26 ms / 2,000 ms
• コード長: 5,455 bytes
• コンパイル時間: 2,124 ms
• コンパイル使用メモリ: 200,408 KB
• 最終ジャッジ日時: 2025-02-09 20:33:53
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 17

ソースコード

#line 1 "test/datastructure/range_set/yuki674.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/674"

#include <iostream>

#line 2 "src/Template.hpp"

#define CUT
#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, l, r) for (int i = (r); i --> (l);)
#define all(c) begin(c), end(c)

#ifdef LOCAL
#define debug(...) debug_impl(#__VA_ARGS__, __VA_ARGS__)
template <class H, class... Ts> void debug_impl(string s, H&& h, Ts&&... ts) {
  cerr << '(' << s << "): (" << forward<H>(h);
  ((cerr << ", " << forward<Ts>(ts)), ..., (cerr << ")\n"));
}
#else
#define debug(...) void(0)
#endif

template <class T> bool chmax(T& a, const T& b) { return b > a ? (a = b, true) : false; }
template <class T> bool chmin(T& a, const T& b) { return b < a ? (a = b, true) : false; }

template <class T> istream& operator>>(istream& in, vector<T>& v) {
  for (auto& e : v) in >> e;
  return in;
}
template <class ...Args> void read(Args&... args) {
  (cin >> ... >> args);
}
template <class T> ostream& operator<<(ostream& out, const vector<T>& v) {
  int n = v.size();
  rep(i, 0, n) {
    out << v[i];
    if (i + 1 != n) out << ' ';
  }
  return out;
}
template <class H, class ...Ts> void print(H&& h, Ts &&... ts) {
  cout << h, ((cout << ' ' << forward<Ts>(ts)), ..., (cout << '\n'));
}

struct io_setup_ {
  io_setup_() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(10);
  }
} io_setup{};
#undef CUT

#define NOTE compile command: \texttt{g++ -std=gnu++17 -Wall -Wextra -g -fsanitize=address -fsanitize=undefined \$\{file\} -o \$\{fileDirname\}/\$\{fileBasenameNoExtension\}}
#undef NOTE
#define NOTE \texttt{-DLOCAL} を加えると \texttt{debug(...)} による出力が有効となる
#undef NOTE
#line 3 "src/datastructure/RangeSet.hpp"
#define CUT
template <class T, bool merge_adj = true>
class RangeSet {
  T siz;
  bool is_mergeable(T cur_r, T next_l) {
    return next_l <= cur_r + merge_adj;
  }
public:
  // mp[l] = r means all of x in [l, r] is a member of this set.
  map<T, T> mp;

  RangeSet(): siz(0) {}

  // returns the number of intergers in this set (not the number of ranges). O(1)
  T number_of_elements() const { return siz; }
  // returns the number of ranges in this set (not the number of integers). O(1)
  int number_of_ranges() const { return mp.size(); }

  // returns whether the given integer is in this set or not. O(log N)
  bool contains(T x) const {
    auto it = mp.upper_bound(x);
    return it != mp.begin() and x <= prev(it)->second;
  }

  /**
   * returns the iterator pointing to the range [l, r] in this set s.t. l <= x <= r.
   * if such a range does not exist, returns `end()`.
   * O(log N)
   */
  auto find_range(T x) const {
    auto it = mp.upper_bound(x);
    return it != mp.begin() and x <= (--it)->second ? it : mp.end();
  }

  // returns whether `x` and `y` is in this set and in the same range. O(log N)
  bool in_the_same_range(T x, T y) const {
    auto it = get_containing_range(x);
    return it != mp.end() and it->first <= y and y <= it->second;
  }

  // inserts the range [x, x] and returns the number of integers inserted to this set. O(log N)
  T insert(T x) {
    return insert(x, x);
  }

  // inserts the range [l, r] and returns the number of integers inserted to this set. amortized O(log N)
  T insert(T l, T r) {
    if (l > r) return 0;
    auto it = mp.upper_bound(l);
    if (it != mp.begin() and is_mergeable(prev(it)->second, l)) {
      it = prev(it);
      l = min(l, it->first);
    }
    T inserted = 0;
    for (; it != mp.end() and is_mergeable(r, it->first); it = mp.erase(it)) {
      auto [cl, cr] = *it;
      r = max(r, cr);
      inserted -= cr - cl + 1;
    }
    inserted += r - l + 1;
    mp[l] = r;
    siz += inserted;
    return inserted;
  }

  // erases the range [x, x] and returns the number of intergers erased from this set. O(log N)
  T erase(T x) {
    return erase(x, x);
  }

  // erases the range [l, r] and returns the number of intergers erased from this set. amortized O(log N)
  T erase(T l, T r) {
    if (l > r) return 0;
    T tl = l, tr = r;
    auto it = mp.upper_bound(l);
    if (it != mp.begin() and l <= prev(it)->second) {
      it = prev(it);
      tl = it->first;
    }
    T erased = 0;
    for (; it != mp.end() and it->first <= r; it = mp.erase(it)) {
      auto [cl, cr] = *it;
      tr = cr;
      erased += cr - cl + 1;
    }
    if (tl < l) {
      mp[tl] = l - 1;
      erased -= l - tl;
    }
    if (r < tr) {
      mp[r + 1] = tr;
      erased -= tr - r;
    }
    siz -= erased;
    return erased;
  }

  // returns minimum integer x s.t. x >= lower and x is NOT in this set
  T minimum_excluded(T lower = 0) const {
    static_assert(merge_adj);
    auto it = find_range(lower);
    return it == mp.end() ? lower : it->second + 1;
  }

  // returns maximum integer x s.t. x <= upper and x is NOT in this set
  T maximum_excluded(T upper) const {
    static_assert(merge_adj);
    auto it = find_range(upper);
    return it == mp.end() ? upper : it->first - 1;
  }
};
#undef CUT
#line 6 "test/datastructure/range_set/yuki674.test.cpp"

int main() {
  long long d;
  int q;
  read(d, q);
  long long ans = 0;
  RangeSet<long long> set;
  while (q-- > 0) {
    long long l, r;
    read(l, r);
    set.insert(l, r);
    auto [nl, nr] = *set.find_range(l);
    chmax(ans, nr - nl + 1);
    print(ans);
  }
  return 0;
}