結果
問題 | No.2574 Defect-free Rectangles |
ユーザー | tonegawa |
提出日時 | 2023-12-05 09:35:46 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 267 ms / 2,000 ms |
コード長 | 11,947 bytes |
コンパイル時間 | 1,971 ms |
コンパイル使用メモリ | 151,924 KB |
実行使用メモリ | 42,112 KB |
最終ジャッジ日時 | 2024-09-27 00:05:56 |
合計ジャッジ時間 | 4,188 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#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);}#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の位置, 無い場合は-1int 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の位置, 無い場合は-1int 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の位置, 無い場合は-1int 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));}// 128bitint 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));}// k番目の1, 無い場合壊れる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);}// k番目の0, 無い場合壊れる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の位置, 無い場合は-1int find_next_128bit(__uint128_t x, int k){__uint128_t b = x >> k;if(!b) return -1;// 末尾64bitが0if(!(b & mask_0_64)) return k + 64 + __builtin_ctzll(b >> 64);return k + __builtin_ctzll(b);}// 0 <= k <= 63// k-bit目以前(kも含む)に初めて現れる1の位置, 無い場合は-1int find_prev_128bit(__uint128_t x, int k){__uint128_t b = x << (127 - k);if(!b) return -1;// 先頭64bitが0if(!(b >> 64)) return k - 64 - __builtin_clzll(b);return k - __builtin_clzll(b >> 64);}// [0, max_elem)template<int max_elem>struct predecessor_problem_small{using ull = unsigned long long;static constexpr ull inf = ~(ull)0;static constexpr int bitlen = 64;static constexpr int bitlen_mod = 63;static constexpr int bitlen_div = 6;static constexpr int block = (max_elem + bitlen - 1) / bitlen;std::array<ull, block> v;predecessor_problem_small(bool f = 0){v.fill(f ? inf : (ull)0);}// O(1)void set(int k, bool f){bool g = (v[k >> bitlen_div] >> (k & bitlen_mod)) & 1;if(f != g) v[k >> bitlen_div] ^= (ull)1 << (k & bitlen_mod);}// O(1)bool get(int k){return (v[k >> bitlen_div] >> (k & bitlen_mod)) & 1;}// O(max_elem / bitlen), ない場合は-1int find_next1(int k){int a = k >> bitlen_div, b = k & bitlen_mod;int res = find_next_64bit(v[a], b);if(res != -1) return (a << bitlen_div) + res < max_elem ? (a << bitlen_div) + res : -1;while(++a < block){if(v[a]){res = (a << bitlen_div) + __builtin_ctzll(v[a]);return res < max_elem ? res : -1;}}return -1;}// O(max_elem / bitlen), ない場合は-1int find_prev1(int k){int a = k >> bitlen_div, b = k & bitlen_mod;int res = find_prev_64bit(v[a], b);if(res != -1) return (a << bitlen_div) + res < max_elem ? (a << bitlen_div) + res : -1;while(--a >= 0){if(v[a]){return (a << bitlen_div) + 63 - __builtin_clzll(v[a]);}}return -1;}};// {begin, end, f: Itr::value_type -> uint}template<typename Itr, typename F>void bucket_sort(Itr first, Itr last, F f){std::vector<std::vector<typename Itr::value_type>> tmp(1);int sz = 1;for(auto itr = first; itr != last; itr++){int key = f(*itr);while(sz <= key) tmp.resize(sz *= 2);tmp[key].push_back(*itr);}int row = 0, col = 0;for(auto itr = first; itr != last; itr++, col++){while(tmp[row].size() <= col) row++, col = 0;*itr = tmp[row][col];}}template<typename Itr, typename F>void bucket_sort2(Itr first, Itr last, F f, int max_elem){static std::vector<std::vector<typename Itr::value_type>> tmp(100000);std::vector<int> idx(max_elem, 0);for(auto itr = first; itr != last; itr++){int key = f(*itr);if(idx[key] == tmp[key].size()){tmp[key].push_back(*itr);idx[key]++;}else tmp[key][idx[key]++] = *itr;}auto itr = first;for(int row = 0; row < max_elem && itr != last; row++){for(int col = 0; col < idx[row]; col++, itr++){*itr = tmp[row][col];}}}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));bucket_sort2(allof(E), [](pair<int, int> &a){return a.first;}, h);reverse(allof(E));int S = w * (w + 1) / 2;predecessor_problem_small<3001> bit;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_prev1(col) + 1;int r = bit.find_next1(col);if(r == -1) r = w;bit.set(col, 1);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';}