結果
問題 | No.2574 Defect-free Rectangles |
ユーザー | tonegawa |
提出日時 | 2023-12-05 09:29:53 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 693 ms / 2,000 ms |
コード長 | 11,797 bytes |
コンパイル時間 | 2,127 ms |
コンパイル使用メモリ | 152,692 KB |
実行使用メモリ | 39,040 KB |
最終ジャッジ日時 | 2024-09-27 00:05:51 |
合計ジャッジ時間 | 6,003 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 3 ms
5,376 KB |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 3 ms
5,376 KB |
testcase_06 | AC | 69 ms
7,424 KB |
testcase_07 | AC | 76 ms
7,424 KB |
testcase_08 | AC | 69 ms
7,424 KB |
testcase_09 | AC | 693 ms
39,040 KB |
testcase_10 | AC | 497 ms
39,040 KB |
testcase_11 | AC | 634 ms
39,040 KB |
testcase_12 | AC | 687 ms
38,912 KB |
testcase_13 | AC | 53 ms
38,784 KB |
testcase_14 | AC | 191 ms
14,720 KB |
testcase_15 | AC | 82 ms
8,576 KB |
testcase_16 | AC | 25 ms
5,376 KB |
ソースコード
#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の位置, 無い場合は-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)); } // 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の位置, 無い場合は-1 int find_next_128bit(__uint128_t x, int k){ __uint128_t b = x >> k; if(!b) return -1; // 末尾64bitが0 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; // 先頭64bitが0 if(!(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), ない場合は-1 int 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), ない場合は-1 int 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){ std::vector<std::vector<typename Itr::value_type>> tmp(max_elem + 1); for(auto itr = first; itr != last; itr++){ int key = f(*itr); 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]; } } 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_sort(allof(E), [](pair<int, int> &a){return a.first;}); 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'; }