#936177 (C++17) No.2574 Defect-free Rectangles

提出ソース
結果

問題	No.2574 Defect-free Rectangles
ユーザー	tonegawa
提出日時	2023-12-04 14:45:01
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	18,506 bytes
コンパイル時間	2,856 ms
コンパイル使用メモリ	173,648 KB
実行使用メモリ	147,092 KB
最終ジャッジ日時	2023-12-04 14:45:10
合計ジャッジ時間	8,829 ms
ジャッジサーバーID （参考情報）	judge12 / judge14
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	3 ms 6,676 KB
testcase_02	AC	2 ms 6,676 KB
testcase_03	AC	5 ms 6,676 KB
testcase_04	AC	5 ms 6,676 KB
testcase_05	AC	5 ms 6,676 KB
testcase_06	AC	568 ms 29,952 KB
testcase_07	AC	495 ms 30,080 KB
testcase_08	AC	444 ms 30,080 KB
testcase_09	TLE	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
権限があれば一括ダウンロードができます
ソースコード

raw source code

#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;
}
long long max(long long a, int b){return std::max(a, (long long)b);}
long long max(int a, long long b){return std::max((long long)a, b);}
long long min(long long a, int b){return std::min(a, (long long)b);}
long long min(int a, long long b){return std::min((long long)a, b);}
long long modulo(long long a, long long m){a %= m; return a < 0 ? a + m : a;}

void io_init(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}






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);
  }
};


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};
  }
  Idx __kth_point(node *v, Idx k){
    while(true){
      Idx lenl = (v->l ? v->l->lensum : 0);
      Idx lenv = lenl + (v->R - v->L);
      if(lenl <= k){
        if(k < lenv) return v->L + (k - lenl);
        k -= lenv;
        v = v->r;
      }else v = v->l;
    }
    return inf;
  }
  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
  Idx kth_point(Idx k){
    return __kth_point(root, k);
  }
  // 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);
  }
  // [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;
  }
  // [l, r)と交差する区間を列挙
  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();
  }
};


int main(){
  io_init();
  int h, w, n;
  std::cin >> h >> w >> n;
  auto v = make_vec<int>(h, w, 0);
  range(i, 0, n){
    int a, b;
    std::cin >> a >> b;
    a--, b--;
    v[a][b] = 1;
  }

  ll ans = 0;
  vector<int> d(w, 0);
  range(i, 0, h){
    range(j, 0, w) d[j] = (v[i][j] ? 0 : d[j] + 1);
    vector<pair<int, int>> E;
    range(j, 0, w) E.push_back({i - d[j], j});
    sort(allof(E));
    reverse(allof(E));

    set_segments<int> seg;
    seg.merge(0, w);
    int S = w * (w + 1) / 2;
    for(int j = i, idx = 0; j >= 0; j--){
      while(idx < E.size() && E[idx].first == j){
        auto [_, col] = E[idx++];
        auto [f, l, r] = seg.find(col);
        seg.erase_intersect(l, r);
        if(l < col) seg.merge(l, col);
        if(col + 1 < r) seg.merge(col + 1, r);
        assert(f);
        int len = r - l;
        S -= len * (len + 1) / 2;
        len = col - l;
        S += len * (len + 1) / 2;
        len = r - (col + 1);
        S += len * (len + 1) / 2;
      }
      ans += S;
    }
  }
  std::cout << ans << '\n';
}
yukicoder

結果

テストケース

ソースコード
