結果

問題 No.674 n連勤
ユーザー tonegawa
提出日時 2023-10-17 15:25:49
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 27 ms / 2,000 ms
コード長 17,085 bytes
コンパイル時間 2,402 ms
コンパイル使用メモリ 158,728 KB
最終ジャッジ日時 2025-02-17 08:11:49
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

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

#line 1 ".lib/template.hpp"
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;
template<typename F, typename S>
std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){
  dest << p.first << ' ' << p.second;
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz;i++){
    int m = v[i].size();
    for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' ');
  }
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T, size_t sz>
std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << *itr;
    itr++;
    if(itr!=v.end()) dest << ' ';
  }
  return dest;
}
template<typename T, typename E>
std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << '(' << itr->first << ", " << itr->second << ')';
    itr++;
    if(itr!=v.end()) dest << '\n';
  }
  return dest;
}
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}
template<typename T>
vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);}
template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail){
  return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}
template<typename T>
vector<T> read_vec(size_t sz){
  std::vector<T> v(sz);
  for(int i=0;i<(int)sz;i++) std::cin >> v[i];
  return v;
}
template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail){
  auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
  for(int i=0;i<(int)sz;i++) v[i] = read_vec<T>(tail...);
  return v;
}
void io_init(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}
#line 1 ".lib/data_structure/range_query/set_segments.hpp"
#line 1 ".lib/data_structure/basic/leftist_heap.hpp"
#line 6 ".lib/data_structure/basic/leftist_heap.hpp"
template<typename Val>
struct leftist_heap{
private:
  struct node{
    node *l, *r;
    int s, sz;
    Val x;
    node(Val x): l(nullptr), r(nullptr), s(0), sz(1), x(x){}
  };
  node *root;
  static int size(node *v){
    return v ? v->sz : 0;
  }
  static bool is_null(node *v){
    return !v || !v->sz;
  }
  static node *meld_inner(node *a, node *b){
    if(is_null(a)) return b;
    if(is_null(b)) return a;
    if(a->x > b->x) std::swap(a, b);
    a->r = meld_inner(a->r, b);
    a->sz = 1 + size(a->l) + size(a->r);
    if(is_null(a->l) || a->l->s < a->r->s) std::swap(a->l, a->r);
    a->s = (is_null(a->r) ? 0 : a->r->s) + 1;
    return a;
  }
public:
  leftist_heap(): root(nullptr){}
  leftist_heap(Val x): root(new node(x)){}
  int size(){
    return (is_null(root) ? 0 : root->sz);
  }
  bool empty(){
    return size() == 0;
  }
  // マージして全要素を移動(永続でないためhの要素は全部消える)
  void meld(leftist_heap<Val> &h){
    root = meld_inner(root, h.root);
    h.root = nullptr;
  }
  Val min(){
    assert(!is_null(root));
    return root->x;
  }
  Val pop_min(){
    assert(!is_null(root));
    Val res = root->x;
    root = meld_inner(root->l, root->r);
    return res;
  }
  void push(Val x){
    root = meld_inner(root, new node(x));
  }
};
template<typename Val>
struct persistent_leftist_heap_iter;
template<typename Val>
struct persistent_leftist_heap{
private:
  struct node{
    node *l, *r;
    int s, sz;
    Val x;
    node(Val x): l(nullptr), r(nullptr), s(0), sz(1), x(x){}
  };
  static int size(node *v){
    return v ? v->sz : 0;
  }
  static bool is_null(node *v){
    return !v || !v->sz;
  }
  static node *copy_node(node *v){
    if(!v) return nullptr;
    return new node(*v);
  }
  static node *meld_inner(node *a, node *b){
    if(is_null(a)) return copy_node(b);
    if(is_null(b)) return copy_node(a);
    if(a->x > b->x) std::swap(a, b);
    a = copy_node(a);
    a->r = meld_inner(a->r, b);
    a->sz = 1 + size(a->l) + size(a->r);
    if(is_null(a->l) || a->l->s < a->r->s) std::swap(a->l, a->r);
    a->s = (is_null(a->r) ? 0 : a->r->s) + 1;
    return a;
  }
  static node *meld_build(node *a, node *b){
    if(is_null(a)) return b;
    if(is_null(b)) return a;
    if(a->x > b->x) std::swap(a, b);
    a->r = meld_inner(a->r, b);
    a->sz = 1 + size(a->l) + size(a->r);
    if(is_null(a->l) || a->l->s < a->r->s) std::swap(a->l, a->r);
    a->s = (is_null(a->r) ? 0 : a->r->s) + 1;
    return a;
  }
public:
  static node *build(const std::vector<Val> &v){
    node *res = nullptr;
    for(auto x : v) res = meld_build(res, new node(x));
    return res;
  }
  static node *make_heap(){
    return nullptr;
  }
  static node *make_heap(Val x){
    return new node(x);
  }
  static node *meld(node *a, node *b){
    return meld_inner(a, b);
  }
  static Val min(node *v){
    assert(size(v));
    return v->x;
  }
  static node *pop_min(node *v){
    assert(size(v));
    return meld(v->l, v->r);
  }
  static node *push(node *v, Val x){
    return meld(v, new node(x));
  }
  friend persistent_leftist_heap_iter<Val>;
};
template<typename Val>
struct persistent_leftist_heap_iter{
  using iter = persistent_leftist_heap_iter<Val>;
  using pheap = persistent_leftist_heap<Val>;
  using node = typename pheap::node;
  node *v;
  persistent_leftist_heap_iter(node *u): v(u){}
public:
  persistent_leftist_heap_iter(): v(nullptr){}
  persistent_leftist_heap_iter(Val x): v(pheap::make_heap(x)){}
  persistent_leftist_heap_iter(const std::vector<Val> &_v): v(pheap::build(_v)){}
  int size(){
    return pheap::size(v);
  }
  bool empty(){
    return size() == 0;
  }
  iter meld(iter &b){
    return pheap::meld(v, b.v);
  }
  Val min(){
    return pheap::min(v);
  }
  iter pop_min(){
    return pheap::pop_min(v);
  }
  iter push(Val x){
    return pheap::push(v, x);
  }
};
#line 4 ".lib/data_structure/range_query/set_segments.hpp"
template<typename Idx, bool merge_adjacent = true>
struct heap_segments{
private:
  leftist_heap<std::pair<Idx, Idx>> h;
  // 左端が最小の区間をマージできる限りマージ
  void __modify(){
    assert(!h.empty());
    auto [l, r] = h.pop_min();
    while(!h.empty() && h.min().first + (!merge_adjacent) <= r){
      r = std::max(r, h.pop_min().second);
    }
    h.push({l, r});
  }
public:
  bool empty(){
    return h.empty();
  }
  // [l, r)をマージ
  // merge_adjacent: [1, 2), [2, 5)のような隣接する区間をマージするか
  void merge(Idx l, Idx r){
    h.push({l, r});
  }
  // 左端が最小の区間　
  std::pair<Idx, Idx> min(){
    __modify();
    return h.min();
  }
  // 左端が最小の区間をpopして返す
  std::pair<Idx, Idx> pop_min(){
    __modify();
    return h.pop_min();
  }
  // 任意の区間に含まれない0以上の最小要素(merge_adjacent = trueのときだけ使える)
  Idx mex(){
    static_assert(merge_adjacent);
    return empty() ? 0 : min().second;
  }
  // rの要素を全て移動(永続でないためrの要素は全て消える)
  void meld(heap_segments &r){
    h.meld(r.h);
  }
};
template<typename Idx, bool merge_adjacent = true>
struct set_segments{
  static constexpr Idx minf = std::numeric_limits<Idx>::min();
  static constexpr Idx inf = std::numeric_limits<Idx>::max();
private:
  struct node{
    int h, sz;
    Idx L, R, lensum;
    node *l, *r;
    node(Idx _L, Idx _R): h(1), sz(1), L(_L), R(_R), lensum(R - L), l(nullptr), r(nullptr){}
    int balanace_factor(){
      return (l ? l->h : 0) - (r ? r->h : 0);
    }
  };
  node *root, *tmp_node;
  int size(node *v){return v ? v->sz : 0;}
  void update(node *v){
    v->h = std::max(v->l ? v->l->h : 0,  v->r ? v->r->h : 0) + 1;
    v->sz = (v->l ? v->l->sz : 0) + (v->r ? v->r->sz : 0) + 1;
    v->lensum = (v->R - v->L) + (v->l ? v->l->lensum : 0) + (v->r ? v->r->lensum : 0);
  }
  node *rotate_right(node *v){
    node *l = v->l;
    v->l = l->r;
    l->r = v;
    update(v);
    update(l);
    return l;
  }
  node *rotate_left(node *v){
    node *r = v->r;
    v->r = r->l;
    r->l = v;
    update(v);
    update(r);
    return r;
  }
  node *balance(node *v){
    int bf = v->balanace_factor();
    assert(-2 <= bf && bf <= 2);
    if(bf == 2){
      if(v->l->balanace_factor() == -1){
        v->l = rotate_left(v->l);
        update(v);
      }
      return rotate_right(v);
    }else if(bf == -2){
      if(v->r->balanace_factor() == 1){
        v->r = rotate_right(v->r);
        update(v);
      }
      return rotate_left(v);
    }
    return v;
  }
  node *leftmost(node *v){
    while(v->l) v = v->l;
    return v;
  }
  node *rightmost(node *v){
    while(v->r) v = v->r;
    return v;
  }
  std::tuple<node*, Idx, Idx> __find(node *v, Idx k){
    Idx Lmax = minf, Rmin = inf;
    while(v){
      if(v->L <= k && k < v->R){
        return {v, v->L, v->R};
      }else if(k < v->L){
        Rmin = v->L;
        v = v->l;
      }else{
        Lmax = v->R;
        v = v->r;
      }
    }
    return {nullptr, Lmax, Rmin};
  }
  node *__kth_segment(node *v, int k){
    while(true){
      int szl = size(v->l);
      if(szl <= k){
        if(szl == k) return v;
        k -= szl + 1;
        v = v->r;
      }else v = v->l;
    }
  }
  int __low_count(node *v, Idx x){
    int res = 0;
    while(v){
      int szl = size(v->l);
      if(x < v->R) v = v->l;
      else v = v->r, res += szl + 1;
    }
    return res;
  }
  Idx __low_count_sum(node *v, Idx x){
    Idx res = 0;
    while(v){
      if(x <= v->L){
        v = v->l;
      }else if(v->R <= x){
        res += (v->l ? v->l->lensum : 0) + (v->R - v->L);
        v = v->r;
      }else{
        return res + (v->l ? v->l->lensum : 0) + (x - v->L);
      }
    }
    return res;
  }
   node *cut_leftmost(node *v){
    if(v->l){
      v->l = cut_leftmost(v->l);
      update(v);
      return balance(v);
    }
    tmp_node = v;
    return v->r;
  }
  node *cut_rightmost(node *v){
    if(v->r){
      v->r = cut_rightmost(v->r);
      update(v);
      return balance(v);
    }
    tmp_node = v;
    return v->l;
  }
  node *__insert(node *v, Idx l, Idx r){
    if(!v) return new node(l, r);
    if(l < v->L){
      v->l = __insert(v->l, l, r);
    }else{
      v->r = __insert(v->r, l, r);
    }
    update(v);
    return balance(v);
  }
  node *__erase(node *v, Idx l){
    if(!v) return nullptr;
    if(l < v->L){
      v->l = __erase(v->l, l);
    }else if(l > v->L){
      v->r = __erase(v->r, l);
    }else{
      if(v->r){
        v->r = cut_leftmost(v->r);
        tmp_node->l = v->l;
        tmp_node->r = v->r;
        free(v);
        update(tmp_node);
        return balance(tmp_node);
      }
      return v->l;
    }
    update(v);
    return balance(v);
  }
  void __merge(Idx l, Idx r){
    auto [L, R] = __erase_intersect(l - merge_adjacent, r + merge_adjacent);
    root = __insert(root, std::min(L, l), std::max(R, r));
  }
  // 消された中で{最小, 最大}
  std::pair<Idx, Idx> __erase_include(Idx l, Idx r){
    Idx emin = inf, emax = minf;
    for(auto [L, R] : enumerate_include(l, r)){
      root = __erase(root, L);
      emin = std::min(emin, L);
      emax = std::max(emax, R);
    }
    return {emin, emax};
  }
  // 消された中で{最小, 最大}
  std::pair<Idx, Idx> __erase_intersect(Idx l, Idx r){
    Idx emin = inf, emax = minf;
    for(auto [L, R] : enumerate_intersect(l, r)){
      root = __erase(root, L);
      emin = std::min(emin, L);
      emax = std::max(emax, R);
    }
    return {emin, emax};
  }
  void __enumerate_include(node *v, Idx l, Idx r, std::vector<std::pair<Idx, Idx>> &res){
    if(!v) return;
    if(v->l && l < v->L) __enumerate_include(v->l, l, r, res);
    if(l <= v->L && v->R <= r) res.push_back({v->L, v->R});
    if(v->r && v->R < r) __enumerate_include(v->r, l, r, res);
  }
  void __enumerate_intersect(node *v, Idx l, Idx r, std::vector<std::pair<Idx, Idx>> &res){
    if(!v) return;
    if(v->l && l < v->L) __enumerate_intersect(v->l, l, r, res);
    if(std::max(l, v->L) < std::min(r, v->R)) res.push_back({v->L, v->R});
    if(v->r && v->R < r) __enumerate_intersect(v->r, l, r, res);
  }
public:
  set_segments(): root(nullptr){}
  int size(){
    return size(root);
  }
  bool empty(){
    return size_sum(root) == 0;
  }
  // a, bが同じ区間に含まれるか
  bool same(Idx a, Idx b){
    auto [v, l, r] = find(a);
    return v && (l == std::get<1>(find(b)));
  }
  // kがいずれかの区間に含まれる場合 {1, L, R}
  // 含まれない場合 {0, L, R} (L, Rはkからいずれの区間にも含まれない座標だけを通って移動できる範囲, 何もない場合は{minf, inf})
  std::tuple<bool, Idx, Idx> find(Idx k){
    auto [v, L, R] = __find(root, k);
    return v ? std::make_tuple(true, L, R) : std::make_tuple(false, L, R);
  }
  std::pair<Idx, Idx> min(){
    assert(size());
    node *v = leftmost(root);
    return {v->L, v->R};
  }
  std::pair<Idx, Idx> max(){
    assert(size());
    node *v = rightmost(root);
    return {v->L, v->R};
  }
  // 任意の区間に含まれないかつa以上の最小要素
  Idx mex(Idx a = 0){
    static_assert(merge_adjacent);
    auto [v, L, R] = find(a);
    return v ? R : a;
  }
  // k番目(0-indexed)に小さい区間. ない場合は{inf, inf}
  std::pair<Idx, Idx> kth_segment(int k){
    if(size() <= k) return {inf, inf};
    node *v = __kth_segment(root, k);
    return {v->L, v->R};
  }
  // [l, r)がr <= xであるような区間の数
  int low_count(Idx x){
    return __low_count(root, x);
  }
  // いずれかの区間に含まれ, かつx未満の座標の数
  Idx low_count_sum(Idx x){
    return __low_count_sum(root, x);
  }
  // [l, r)をマージ
  // merge_adjacent: [1, 2), [2, 5)のような隣接する区間をマージするか
  void merge(Idx l, Idx r){
    __merge(l, r);
  }
  // [l, r)に含まれる区間を削除
  void erase_include(Idx l, Idx r){
    __erase_include(l, r);
  }
  // [l, r)と少しでも交差する区間を削除
  void erase_intersect(Idx l, Idx r){
    __erase_intersect(l, r);
  }
  std::vector<std::pair<Idx, Idx>> enumerate_include(Idx l, Idx r){
    std::vector<std::pair<Idx, Idx>> res;
    __enumerate_include(root, l, r, res);
    return res;
  }
  std::vector<std::pair<Idx, Idx>> enumerate_intersect(Idx l, Idx r){
    std::vector<std::pair<Idx, Idx>> res;
    __enumerate_intersect(root, l, r, res);
    return res;
  }
  std::vector<std::pair<Idx, Idx>> enumerate_all(){
    return enumerate_intersect(minf, inf);
  }
  void clear(){
    root = nullptr;
  }
  void swap(set_segments<Idx> &r){
    std::swap(root, r.root);
  }
  // rの要素を全て移動(永続でないためrの要素は全て消える)
  void meld(set_segments<Idx> &r){
    if(size() < r.size()) swap(r);
    for(auto [L, R] : r.enumerate_all()) merge(L, R);
    r.clear();
  }
};
#line 3 "a.cpp"
int main(){
  io_init();
  ll d, q;
  std::cin >> d >> q;
  set_segments<ll> st;
  ll ans = 0;
  range(i, 0, q){
    ll l, r;
    std::cin >> l >> r;
    st.merge(l, r + 1);
    auto [V, L, R] = st.find(l);
    ans = max(ans, R - L);
    std::cout << ans << '\n';
  }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0