結果

問題 No.2574 Defect-free Rectangles
ユーザー tonegawa
提出日時 2023-12-04 14:52:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,266 ms / 2,000 ms
コード長 36,702 bytes
コンパイル時間 1,927 ms
コンパイル使用メモリ 154,804 KB
最終ジャッジ日時 2025-02-18 07:10:25
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

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

#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, Rk, {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();
}
};
#include <stdint.h>
static constexpr __uint128_t mask_0_64 = ((__uint128_t)1 << 64) - 1;
//static constexpr uint64_t mask_32_64 = 0xFFFFFFFF00000000;
static constexpr uint64_t mask_0_32 = 0x00000000FFFFFFFF;
static constexpr uint64_t mask_48_64 = 0xFFFF000000000000;
static constexpr uint64_t mask_32_48 = 0x0000FFFF00000000;
static constexpr uint64_t mask_16_32 = 0x00000000FFFF0000;
static constexpr uint64_t mask_0_16 = 0x000000000000FFFF;
static constexpr int TABLE_SIZE_LOG = 16, TABLE_SIZE = 1 << TABLE_SIZE_LOG;
using __table = std::vector<std::array<int8_t, TABLE_SIZE_LOG>>;
using __table_p = std::vector<std::array<std::pair<int8_t, int8_t>, TABLE_SIZE_LOG>>;
__table select_build(){
__table res(TABLE_SIZE);
for(int i = 0; i < TABLE_SIZE; i++){
res[i].fill(-1);
int pcnt = 0;
for(int j = 0; j < TABLE_SIZE_LOG; j++) if((i >> j) & 1) res[i][pcnt++] = j;
}
return res;
}
// k-bit(k)1, -1
int find_next_32bit(uint32_t x, int k){
uint32_t b = x >> k;
if(!b) return -1;
return k + __builtin_ctz(b);
}
// k-bit(k)1, -1
int find_next_64bit(uint64_t x, int k){
uint64_t b = x >> k;
if(!b) return -1;
return k + __builtin_ctzll(b);
}
// 0 <= k <= 63
// k-bit(k)1, -1
int find_prev_64bit(uint64_t x, int k){
uint64_t b = x << (63 - k);
if(!b) return -1;
return k - __builtin_clzll(b);
}
// k(0-indexed)1(0-indexed).
int select_32bit(uint32_t x, int k){
static __table table = select_build();
int r = __builtin_popcount(x & mask_0_16);
if(r > k) return table[x & mask_0_16][k];
return 16 + table[(x & mask_16_32) >> 16][k - r];
}
// k(0-indexed)1(0-indexed).
int select_64bit(uint64_t x, int k){
static __table table = select_build();
int r = __builtin_popcount(x & mask_0_32);
if(r > k){
int rr = __builtin_popcount(x & mask_0_16);
if(rr > k) return table[x & mask_0_16][k];
else return 16 + table[(x & mask_16_32) >> 16][k - rr];
}else{
k -= r;
int lr = __builtin_popcountll(x & mask_32_48);
if(lr > k) return 32 + table[(x & mask_32_48) >> 32][k];
else return 48 + table[(x & mask_48_64) >> 48][k - lr];
}
}
// k_bit(0 <= k <= 32)1
int rank_32bit(uint32_t x, int k){
return k == 32 ? __builtin_popcount(x) : __builtin_popcount(x & ((1ULL << k) - 1));
}
// k_bit(0 <= k <= 64)1
int rank_64bit(uint64_t x, int k){
return k == 64 ? __builtin_popcountll(x) : __builtin_popcountll(x & ((1ULL << k) - 1));
}
// 128bit
int pop_count_128bit(__uint128_t x){
return __builtin_popcountll(x >> 64) + __builtin_popcountll(x & mask_0_64);
}
int rank_128bit(__uint128_t x, int k){
if(k == 128) return pop_count_128bit(x);
if(k < 64) return __builtin_popcountll((x & mask_0_64) & ((1ULL << k) - 1));
k -= 64;
return __builtin_popcountll(x & mask_0_64) + __builtin_popcountll((x >> 64) & ((1ULL << k) - 1));
}
// k1,
int select1_128bit(__uint128_t x, int k){
int left_pop = __builtin_popcountll(x & mask_0_64);
if(left_pop > k) return select_64bit(x & mask_0_64, k);
return 64 + select_64bit(x >> 64, k - left_pop);
}
// k0,
int select0_128bit(__uint128_t x, int k){
__uint128_t y = ~x;
int left_unpop = __builtin_popcountll(y & mask_0_64);
if(left_unpop > k) return select_64bit(y & mask_0_64, k);
return 64 + select_64bit(y >> 64, k - left_unpop);
}
// k-bit(k)1, -1
int find_next_128bit(__uint128_t x, int k){
__uint128_t b = x >> k;
if(!b) return -1;
// 64bit0
if(!(b & mask_0_64)) return k + 64 + __builtin_ctzll(b >> 64);
return k + __builtin_ctzll(b);
}
// 0 <= k <= 63
// k-bit(k)1, -1
int find_prev_128bit(__uint128_t x, int k){
__uint128_t b = x << (127 - k);
if(!b) return -1;
// 64bit0
if(!(b >> 64)) return k - 64 - __builtin_clzll(b);
return k - __builtin_clzll(b >> 64);
}
template<typename Val = long long>
struct binary_indexed_tree{
int M, H;
std::vector<Val> sum;
binary_indexed_tree(){}
binary_indexed_tree(int N): M(N), H(31 - __builtin_clz(M)), sum(M + 1 , 0){}
binary_indexed_tree(const std::vector<Val> &v): M(v.size()), H(31 - __builtin_clz(M)), sum(1){
sum.insert(sum.begin() + 1, v.begin(), v.end());
for(int i = 1; i <= v.size(); i++){
int nxt = i + (i & (-i));
if(nxt <= M) sum[nxt] += sum[i];
}
}
void update(int k, Val x){
for(int i = k + 1; i <= M; i += (i & (-i))) sum[i] += x;
}
Val query(int r){
Val ret = 0;
for(int k = r; k > 0; k -= (k & (-k))) ret += sum[k];
return ret;
}
Val query(int l, int r){
return query(r) - query(l);
}
// sum[0, k]xksum[0, k], {M, }
// sum調
using p = std::pair<int, Val>;
p lower_bound(Val x){
int v = 1 << H, h = H;
Val s = 0, t = 0;
while(h--){
if(M < v) v -= 1 << h;
else if(x <= s + sum[v]) t = s + sum[v], v -= 1 << h;
else s += sum[v], v += 1 << h;
}
if(v == M + 1) return {M, s};
return (x <= s + sum[v] ? p{v - 1, s + sum[v]} : p{v, t});
}
};
// bitset
// resize
// n, m, im: , , (1)
// rank, selectbinary_indexed_tree
struct dynamic_bitset_rank_select{
static constexpr int BITLEN = 64, REM = 63, SHIFT = 6;
int n, m, im;
std::vector<uint64_t> v;
binary_indexed_tree<int> bit_count;
uint64_t rightmost_mask(){
return !(n & REM) ? ~0ULL : (1ULL << (n & REM)) - 1;
}
dynamic_bitset_rank_select(): n(0), m(0), im(0){}
dynamic_bitset_rank_select(const dynamic_bitset_rank_select &r): n(r.n), m(r.m),
im(r.im), v(r.v.begin(), r.v.begin() + r.im), bit_updated(false){}
dynamic_bitset_rank_select(int n, bool f = 0): n(n), m((n + REM) >> SHIFT), bit_updated(false){
if(f){
im = m;
v.resize(m, ~0ULL);
v.back() &= rightmost_mask();
}else im = 0;
}
// string0bit
dynamic_bitset_rank_select(const std::string &s, char one = '1'): n(s.size()), m((n + REM) >> SHIFT), im(0), bit_updated(false){
uint64_t sum = 0;
for(int i = 0, j = 0, t = 0; i < n; i++){
sum += (uint64_t)(s[i] == one) << j;
if(i == n - 1 || j == REM){
t++;
v.push_back(sum);
if(sum) im = t;
sum = j = 0;
}else j++;
}
}
int size(){
return n;
}
void set(int k, bool f){
assert(0 <= k && k < n);
int block = k >> SHIFT;
if(f){
if(block >= im) im = block + 1;
while(block >= v.size()) v.resize(std::min((int)v.size() * 2 + 1, m), 0);
if(bit_updated && !((v[block] >> (k & REM)) & 1)) bit_count.update(block, 1);
v[block] |= (1ULL << (k & REM));
}else if(block < im){
if(bit_updated && ((v[block] >> (k & REM)) & 1)) bit_count.update(block, -1);
v[block] &= ~(1ULL << (k & REM));
}
}
bool get(int k){
return (k >> SHIFT) < im ? (v[k >> SHIFT] >> (k & REM)) & 1 : 0;
}
bool any(){
if(bit_updated) return bit_count.query(m);
for(int i = 0; i < im; i++) if(v[i]) return true;
return false;
}
bool all(){
if(bit_updated) return bit_count.query(m) == n;
if(im != m) return false;
for(int i = 0; i < m - 1; i++) if(v[i] != ~0ULL) return false;
if(v[m - 1] != rightmost_mask()) return false;
return true;
}
bool none(){
return !any();
}
/*
void resize(int s){
bit_updated = false;
m = (s + REM) >> SHIFT;
if(m < im) v.resize(m), im = m;
n = s;
if(m == im) v[m - 1] &= rightmost_mask();
}
*/
dynamic_bitset_rank_select operator ~(){
dynamic_bitset_rank_select res = *this;
res.v.resize(m, ~0ULL);
for(int i = 0; i < res.im; i++) res.v[i] = ~res.v[i];
res.im = res.m;
res.v[m - 1] &= res.rightmost_mask();
return res;
}
dynamic_bitset_rank_select operator ^ (const dynamic_bitset_rank_select &r){
dynamic_bitset_rank_select res(*this);
return res ^= r;
}
dynamic_bitset_rank_select operator | (const dynamic_bitset_rank_select &r){
dynamic_bitset_rank_select res(*this);
return res |= r;
}
dynamic_bitset_rank_select operator & (const dynamic_bitset_rank_select &r){
dynamic_bitset_rank_select res(*this);
return res &= r;
}
dynamic_bitset_rank_select operator ^= (const dynamic_bitset_rank_select &r){
assert(n == r.n);
bit_updated = false;
if(im < r.im){
im = r.im;
v.resize(r.im, 0);
}
for(int i = 0; i < r.im; i++) v[i] ^= r.v[i];
return *this;
}
dynamic_bitset_rank_select operator |= (const dynamic_bitset_rank_select &r){
assert(n == r.n);
bit_updated = false;
if(im < r.im){
im = r.im;
v.resize(r.im, 0);
}
for(int i = 0; i < r.im; i++) v[i] |= r.v[i];
return *this;
}
dynamic_bitset_rank_select operator &= (const dynamic_bitset_rank_select &r){
assert(n == r.n);
bit_updated = false;
if(im > r.im){
im = r.im;
v.resize(im);
}
for(int i = 0; i < im; i++) v[i] &= r.v[i];
return *this;
}
// ,
bool operator == (const dynamic_bitset_rank_select &r){
if(n != r.n) return false;
for(int i = 0; i < std::min(im, r.im); i++) if(v[i] != r.v[i]) return false;
if(im > r.im){
for(int i = r.im; i < im; i++) if(v[i]) return false;
}else{
for(int i = im; i < r.im; i++) if(r.v[i]) return false;
}
return true;
}
bool operator != (const dynamic_bitset_rank_select &r){
return !(*this == r);
}
// l |= r << s, l = rok
static void lshift_or(dynamic_bitset_rank_select &l, dynamic_bitset_rank_select &r, int s){
assert(l.n == r.n);
l.bit_updated = false;
int t = s & REM, k = s >> SHIFT;
if(!t){
int imr = std::min(r.m, r.im + k);
l.im = std::max(l.im, imr);
if(imr > l.v.size()) l.v.resize(imr, 0);
for(int i = imr - 1; i >= k; i--) l.v[i] |= r.v[i - k];
if(imr == l.m) l.v.back() &= l.rightmost_mask();
return;
}
int imr = std::min(r.m, r.im + k + 1);
l.im = std::max(l.im, imr);
if(imr > l.v.size()) l.v.resize(imr, 0);
int upper_bit = 64 - t;
for(int i = imr - 1; i >= k; i--){
if(i == k) l.v[i] |= r.v[i - k] << t;
else l.v[i] |= (r.v[i - k] << t) | (r.v[i - k - 1] >> upper_bit);
}
if(imr == l.m) l.v.back() &= l.rightmost_mask();
}
// l ^= r << s, l = rok
static void lshift_xor(dynamic_bitset_rank_select &l, dynamic_bitset_rank_select &r, int s){
assert(l.n == r.n);
l.bit_updated = false;
int t = s & REM, k = s >> SHIFT;
if(!t){
int imr = std::min(r.m, r.im + k);
l.im = std::max(l.im, imr);
if(imr > l.v.size()) l.v.resize(imr, 0);
for(int i = imr - 1; i >= k; i--) l.v[i] ^= r.v[i - k];
if(imr == l.m) l.v.back() &= l.rightmost_mask();
return;
}
int imr = std::min(r.m, r.im + k + 1);
l.im = std::max(l.im, imr);
if(imr > l.v.size()) l.v.resize(imr, 0);
int upper_bit = 64 - t;
for(int i = imr - 1; i >= k; i--){
if(i == k) l.v[i] ^= r.v[i - k] << t;
else l.v[i] ^= (r.v[i - k] << t) | (r.v[i - k - 1] >> upper_bit);
}
if(imr == l.m) l.v.back() &= l.rightmost_mask();
}
// l &= r << s, l = rok
static void lshift_and(dynamic_bitset_rank_select &l, dynamic_bitset_rank_select &r, int s){
assert(l.n == r.n);
l.bit_updated = false;
int t = s & REM, k = s >> SHIFT;
if(!t){
int imr = std::min(l.im, r.im + k);
for(int i = imr - 1; i >= 0; i--) l.v[i] &= (i >= k ? r.v[i - k] : 0);
for(int i = l.im - 1; i >= imr; i--) l.v[i] = 0;
l.im = imr;
return;
}
int imr = std::min(l.im, r.im + k + 1);
int upper_bit = 64 - t;
for(int i = imr - 1; i >= 0; i--){
if(i < k) l.v[i] = 0;
else if(i == k) l.v[i] &= r.v[i - k] << t;
else l.v[i] &= (r.v[i - k] << t) | (r.v[i - k - 1] >> upper_bit);
}
for(int i = l.im - 1; i >= imr; i--) l.v[i] = 0;
l.im = imr;
}
dynamic_bitset_rank_select operator <<= (const int s){
assert(0 <= s);
bit_updated = false;
int t = s & REM, k = s >> SHIFT;
if(!t){
im = std::min(m, im + k);
if(im > v.size()) v.resize(im, 0);
for(int i = im - 1; i >= 0; i--) v[i] = (i >= k ? v[i - k] : 0);
if(im == m) v.back() &= rightmost_mask();
return *this;
}
im = std::min(m, im + k + 1);
if(im > v.size()) v.resize(im, 0);
int upper_bit = 64 - t;
for(int i = im - 1; i >= 0; i--){
if(i < k) v[i] = 0;
else if(i == k) v[i] = v[i - k] << t;
else v[i] = (v[i - k] << t) | (v[i - k - 1] >> upper_bit);
}
if(im == m) v.back() &= rightmost_mask();
return *this;
}
dynamic_bitset_rank_select operator >>= (const int s){
assert(0 <= s);
bit_updated = false;
int t = s & REM, k = s >> SHIFT;
im -= k;
if(!t){
for(int i = 0; i < im; i++) v[i] = v[i + k];
for(int i = std::max(0, im); i < im + k; i++) v[i] = 0;
if(im < 0) im = 0;
return *this;
}
int upper_bit = 64 - t;
for(int i = 0; i < im; i++){
if(i + k == (int)v.size() - 1) v[i] = v[i + k] >> t;
else v[i] = (v[i + k] >> t) | (v[i + k + 1] << upper_bit);
}
for(int i = std::max(0, im); i < im + k; i++) v[i] = 0;
if(im < 0) im = 0;
return *this;
}
dynamic_bitset_rank_select operator << (const int s){
dynamic_bitset_rank_select res(*this);
return res <<= s;
}
dynamic_bitset_rank_select operator >> (const int s){
dynamic_bitset_rank_select res(*this);
return res >>= s;
}
bool bit_updated;
void bit_recalc(){
if(bit_updated) return;
if(bit_count.sum.size() != m + 1) bit_count = binary_indexed_tree<int>(m);
for(int i = 0; i < m; i++){
if(i < im) bit_count.sum[i + 1] = __builtin_popcountll(v[i]);
else bit_count.sum[i + 1] = 0;
}
for(int i = 1; i <= m; i++){
int nxt = i + (i & (-i));
if(nxt <= m) bit_count.sum[nxt] += bit_count.sum[i];
}
bit_updated = true;
}
int pop_count(){
if(!bit_updated) bit_recalc();
return bit_count.query(m);
}
int rank1(int r){
assert(0 <= r && r <= n);
if(!bit_updated) bit_recalc();
int block = r >> SHIFT;
return bit_count.query(block) + (im <= block ? 0 : rank_64bit(v[block], r & REM));
}
int rank0(int r){
assert(0 <= r && r <= n);
return r - rank1(r);
}
// k(0-indexed)1, -1
int select1(int k){
if(!bit_updated) bit_recalc();
auto [b, c] = bit_count.lower_bound(k + 1);
if(b == m) return -1;
return (b << SHIFT) + select_64bit(v[b], k - c + __builtin_popcountll(v[b]));
}
// k(0-indexed)0, -1
int select0(int k){
if(!bit_updated) bit_recalc();
int x = k + 1, y = 1 << bit_count.H, h = bit_count.H;
int s = 0, t = 0;
while(h--){
if(bit_count.M < y) y -= 1 << h;
else{
int sum_zero = s + (1 << (h + 1 + SHIFT)) - bit_count.sum[y]; // = 2^(h + 1) * 64 = 1 << (h + 1 + SHIFT)
if(x <= sum_zero) t = sum_zero, y -= 1 << h;
else s = sum_zero, y += 1 << h;
}
}
if(y == bit_count.M + 1) return -1;
int b, c;
if(x <= s + (1 << SHIFT) - bit_count.sum[y]) b = y - 1, c = s + (1 << SHIFT) - bit_count.sum[y];
else b = y, c = t;
int i = (b << SHIFT);
if(b >= im) i += k - c + BITLEN;
else i += select_64bit(~v[b], k - c + __builtin_popcountll(~v[b]));
return i >= n ? -1 : i;
}
// i(i)1, -1
int find_next1(int i){
assert(0 <= i && i < n);
if((i >> SHIFT) >= im) return -1;
int _i = i & REM, _j = find_next_64bit(v[i >> SHIFT], _i);
if(_j != -1) return i - _i + _j;
return select1(rank1(i));
}
// i(i)1, -1
int find_prev1(int i){
assert(0 <= i && i < n);
if((i >> SHIFT) >= im){
if(!im) return -1;
i = (im << SHIFT) - 1;
}
int _i = i & REM, _j = find_prev_64bit(v[i >> SHIFT], _i);
if(_j != -1) return i - _i + _j;
int r = rank1(i + 1);
if(!r) return -1;
return select1(r - 1);
}
// i(i)0, -1
int find_next0(int i){
assert(0 <= i && i < n);
if((i >> SHIFT) >= im) return i;
int _i = i & REM, _j = find_next_64bit(~v[i >> SHIFT], _i);
if(_j != -1){
int res = i - _i + _j;
return res >= n ? -1 : res;
}
return select0(rank0(i));
}
// i(i)0, -1
int find_prev0(int i){
assert(0 <= i && i < n);
if((i >> SHIFT) >= im) return i;
int _i = i & REM, _j = find_prev_64bit(~v[i >> SHIFT], _i);
if(_j != -1) return i - _i + _j;
int r = rank0(i + 1);
if(!r) return -1;
return select0(r - 1);
}
};
std::ostream &operator<<(std::ostream &dest, const dynamic_bitset_rank_select &v){
if(!v.n) return dest;
int cnt = 0;
for(int i = 0; i < v.m; i++){
if(i >= v.im){
for(int j = 0; j < 64 && cnt < v.n; j++, cnt++) dest << 0;
}else{
for(int j = 0; j < 64 && cnt < v.n; j++, cnt++) dest << ((v.v[i] >> j) & 1);
}
if(i != v.m - 1) dest << ' ';
}
return dest;
}
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) if(i >= d[j]) E.push_back({i - d[j], j});
sort(allof(E));
reverse(allof(E));
int S = w * (w + 1) / 2;
/*
set_segments<int> seg;
seg.merge(0, w);
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);
S -= (r - l) * (r - l + 1) / 2;
S += (col - l) * (col - l + 1) / 2;
S += (r - col - 1) * (r - col) / 2;
}
ans += S;
}
*/
dynamic_bitset_rank_select bit(w, 1);
for(int j = i, idx = 0; j >= 0; j--){
while(idx < E.size() && E[idx].first == j){
auto [_, col] = E[idx++];
int l = bit.find_prev0(col) + 1;
int r = bit.find_next0(col);
if(r == -1) r = w;
bit.set(col, 0);
S -= (r - l) * (r - l + 1) / 2;
S += (col - l) * (col - l + 1) / 2;
S += (r - col - 1) * (r - col) / 2;
}
ans += S;
}
}
std::cout << ans << '\n';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0