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

提出ソース
結果

問題	No.674 n連勤
ユーザー	tonegawa
提出日時	2023-10-17 15:23:56
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	95 ms / 2,000 ms
コード長	17,072 bytes
コンパイル時間	2,277 ms
コンパイル使用メモリ	164,952 KB
実行使用メモリ	5,608 KB
最終ジャッジ日時	2023-10-17 15:24:09
合計ジャッジ時間	4,027 ms
ジャッジサーバーID （参考情報）	judge14 / judge13
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	2 ms 4,348 KB
testcase_05	AC	2 ms 4,348 KB
testcase_06	AC	2 ms 4,348 KB
testcase_07	AC	2 ms 4,348 KB
testcase_08	AC	2 ms 4,348 KB
testcase_09	AC	2 ms 4,348 KB
testcase_10	AC	2 ms 4,348 KB
testcase_11	AC	8 ms 4,348 KB
testcase_12	AC	8 ms 4,348 KB
testcase_13	AC	73 ms 5,608 KB
testcase_14	AC	76 ms 5,608 KB
testcase_15	AC	72 ms 5,600 KB
testcase_16	AC	95 ms 5,468 KB
testcase_17	AC	93 ms 5,472 KB
testcase_18	AC	87 ms 4,792 KB
testcase_19	AC	76 ms 5,608 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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(){
  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';
  }
}
yukicoder

結果

テストケース

ソースコード
