結果

問題 No.2574 Defect-free Rectangles
ユーザー tonegawatonegawa
提出日時 2023-12-05 09:37:34
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 276 ms / 2,000 ms
コード長 12,020 bytes
コンパイル時間 1,692 ms
コンパイル使用メモリ 153,408 KB
実行使用メモリ 39,936 KB
最終ジャッジ日時 2024-09-27 00:06:00
合計ジャッジ時間 3,608 ms
ジャッジサーバーID
（参考情報） 		judge3 / 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 2 ms
5,376 KB
testcase_04 AC 4 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 44 ms
8,320 KB
testcase_07 AC 25 ms
7,552 KB
testcase_08 AC 24 ms
7,424 KB
testcase_09 AC 264 ms
39,680 KB
testcase_10 AC 158 ms
38,784 KB
testcase_11 AC 266 ms
39,936 KB
testcase_12 AC 276 ms
39,936 KB
testcase_13 AC 50 ms
38,656 KB
testcase_14 AC 86 ms
15,232 KB
testcase_15 AC 49 ms
9,344 KB
testcase_16 AC 20 ms
5,504 KB
権限があれば一括ダウンロードができます

ソースコード

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



#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];
  }
}

// keyが[0, max_elem)
template<typename Itr, typename F>
void bucket_sort_fast(Itr first, Itr last, F f, int max_elem){
  static std::vector<std::vector<typename Itr::value_type>> tmp;
  if(tmp.size() < max_elem) tmp.resize(max_elem);
  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_sort_fast(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';
}
0