#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define allof(obj) (obj).begin(), (obj).end() #define range(i, l, r) for(int i=l;i>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; using pl = std::pair; using namespace std; template std::ostream &operator<<(std::ostream &dest, const std::pair &p){ dest << p.first << ' ' << p.second; return dest; } template std::ostream &operator<<(std::ostream &dest, const std::vector> &v){ int sz = v.size(); if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::vector &v){ int sz = v.size(); if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::array &v){ if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::set &v){ for(auto itr=v.begin();itr!=v.end();){ dest << *itr; itr++; if(itr!=v.end()) dest << ' '; } return dest; } template std::ostream &operator<<(std::ostream &dest, const std::map &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 vector make_vec(size_t sz, T val){return std::vector(sz, val);} template auto make_vec(size_t sz, Tail ...tail){ return std::vector(tail...))>(sz, make_vec(tail...)); } template vector read_vec(size_t sz){ std::vector v(sz); for(int i=0;i<(int)sz;i++) std::cin >> v[i]; return v; } template auto read_vec(size_t sz, Tail ...tail){ auto v = std::vector(tail...))>(sz); for(int i=0;i<(int)sz;i++) v[i] = read_vec(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 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>; using __table_p = std::vector, 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 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 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 void bucket_sort(Itr first, Itr last, F f){ std::vector> 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]; } } // keyが[0, max_elem) template void bucket_sort_fast(Itr first, Itr last, F f, int max_elem){ static std::vector> tmp; if(tmp.size() < max_elem) tmp.resize(max_elem); std::vector 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(h, w, 0); range(i, 0, n){ int a, b; std::cin >> a >> b; a--, b--; v[a][b] = 1; } ll ans = 0; vector d(w, 0); range(i, 0, h){ range(j, 0, w) d[j] = (v[i][j] ? 0 : d[j] + 1); vector> E; range(j, 0, w) if(i >= d[j]) E.push_back({i - d[j], j}); //sort(allof(E)); bucket_sort_fast(allof(E), [](pair &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'; }