Submission #23120967

---

Source Code Expand

#pragma GCC target("popcnt")

#include <algorithm>
#include <array>
#include <climits>
#include <cstdint>
#include <utility>
#include <vector>

namespace wavelet_matrix_2d_impl {

using u32 = std::uint32_t;
using u64 = std::uint64_t;

u32 popcount(u32 x) {
#ifdef __GNUC__
  static_assert(CHAR_BIT * sizeof(int) >= 32);
  return __builtin_popcount(x);
#else
  x -= x >> 1 & 0x55555555;
  x = (x & 0x33333333) + (x >> 2 & 0x33333333);
  x = (x + (x >> 4)) & 0x0F0F0F0F;
  return x * 0x01010101 >> 24 & 0x3F;
#endif
}

u32 bit_width(u32 c) noexcept {
#ifdef __GNUC__
  static_assert(CHAR_BIT * sizeof(int) >= 32);
  if (c == 0) {
    return 0;
  } else {
    return CHAR_BIT * sizeof(int) - __builtin_clz(c);
  }
#else
  static constexpr std::array<std::uint8_t, 32> table = {
      0,  1, 2,  6,  3,  11, 7,  16, 4,  14, 12, 21, 8,  23, 17, 26,
      31, 5, 10, 15, 13, 20, 22, 25, 30, 9,  19, 24, 29, 18, 28, 27};
  if (c >> 31) {
    return 32;
  }
  c |= c >> 1;
  c |= c >> 2;
  c |= c >> 4;
  c |= c >> 8;
  c |= c >> 16;
  return table[(c + 1) * 0x4653ADF >> 27 & 0x1F];
#endif
}

class bit_vector {
  class node_type {
  public:
    u32 bit;
    u32 sum;

    node_type() : bit(0), sum(0) {}
  };

  std::vector<node_type> v;

public:
  bit_vector(const u32 n) : v(n / 32 + 1) {}
  void set(const u32 i) {
    node_type &node = v[i / 32];
    node.bit |= static_cast<u32>(1) << i % 32;
    node.sum += 1;
  }
  void build() {
    for (u32 i = v.size(); i != 1;) {
      i -= 1;
      v[i - 1].sum += v[i].sum;
    }
  }

  u32 rank(const u32 i) const {
    const node_type &node = v[i / 32];
    return node.sum - popcount(node.bit & (static_cast<u32>(1) << i % 32) - 1);
  }
  u32 all() const { return v.front().sum; }
};

class wavelet_matrix {
  std::vector<bit_vector> matrix;

public:
  wavelet_matrix() : matrix() {}
  wavelet_matrix(std::vector<u32> a) : matrix() {
    const u32 n = a.size();
    u32 p = 0;
    for (const auto &e : a) {
      p = std::max(p, bit_width(e));
    }
    matrix.assign(p, n);
    std::vector<u32> b;
    b.reserve(n);
    while (p != 0) {
      p -= 1;
      bit_vector &bv = matrix[p];
      u32 k = 0;
      for (u32 i = 0; i != n; i += 1) {
        if (a[i] >> p & 1) {
          b.push_back(a[i]);
        } else {
          bv.set(i);
          a[k] = a[i];
          k += 1;
        }
      }
      std::copy(b.begin(), b.end(), a.begin() + k);
      b.clear();
      bv.build();
    }
  }
  u32 less_than(u32 l, u32 r, const u32 x) const {
    u32 p = matrix.size();
    if (p != 32 && x >> p) {
      return r - l;
    }
    u32 ret = 0;
    while (p != 0) {
      p -= 1;
      const bit_vector &bv = matrix[p];
      const u32 cl = bv.rank(l);
      const u32 cr = bv.rank(r);
      const u32 z = bv.all();
      if (x >> p & 1) {
        ret += cl - cr;
        l = l + cl;
        r = r + cr;
      } else {
        l = z - cl;
        r = z - cr;
      }
    }
    return ret;
  }
  u32 count(const u32 l, const u32 r, const u32 d, const u32 u) const {
    return less_than(l, r, u) - less_than(l, r, d);
  }
};

template <class T> class compress {
  std::vector<T> v;

public:
  compress() : v() {}
  void reserve(const u32 n) { v.reserve(n); }
  void push(const T &x) { v.push_back(x); }
  void build() {
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
  }
  u32 operator()(const T &x) const {
    return std::lower_bound(v.begin(), v.end(), x) - v.begin();
  }
  const T &operator[](const u32 i) const { return v[i]; }
};

template <class X, class Y> class wavelet_matrix_2d {
  compress<X> cx;
  compress<Y> cy;
  std::vector<std::pair<bit_vector, wavelet_matrix>> matrix;

public:
  wavelet_matrix_2d(const std::vector<std::pair<X, Y>> &a_)
      : cx(), cy(), matrix() {
    const u32 n = a_.size();
    u32 p = 0;
    auto a = [&]() {
      cx.reserve(n);
      cy.reserve(n);
      for (const auto &[x, y] : a_) {
        cx.push(x);
        cy.push(y);
      }
      cx.build();
      cy.build();
      std::vector<std::pair<u32, u32>> a(n);
      for (u32 i = 0; i != n; i += 1) {
        const auto &[x, y] = a_[i];
        a[i] = {cx(x), cy(y)};
        p = std::max(p, bit_width(a[i].second));
      }
      return a;
    }();
    std::vector<std::pair<u32, u32>> b;
    b.reserve(n);
    matrix.assign(p, {{n}, {}});
    while (p != 0) {
      p -= 1;
      auto &[bv, wm] = matrix[p];
      u32 k = 0;
      for (u32 i = 0; i != n; i += 1) {
        if (a[i].second >> p & 1) {
          b.push_back(a[i]);
        } else {
          bv.set(i);
          a[k] = a[i];
          k += 1;
        }
      }
      std::copy(b.begin(), b.end(), a.begin() + k);
      b.clear();
      std::vector<u32> c(n);
      for (u32 i = 0; i != n; i += 1) {
        c[i] = a[i].first;
      }
      bv.build();
      wm = wavelet_matrix(std::move(c));
    }
  }

  const Y &quantile(u32 l, u32 r, const X &d_, const X &u_, u32 k) const {
    const u32 d = cx(d_);
    const u32 u = cx(u_);
    u32 ret = 0;
    for (u32 p = matrix.size(); p != 0;) {
      p -= 1;
      const auto &[bv, wm] = matrix[p];
      const u32 cl = bv.rank(l);
      const u32 cr = bv.rank(r);
      const u32 z = bv.all();
      const u32 c = wm.count(z - cl, z - cr, d, u);
      if (k < c) {
        l = z - cl;
        r = z - cr;
      } else {
        k -= c;
        l = l + cl;
        r = r + cr;
        ret |= static_cast<u32>(1) << p;
      }
    }
    return cy[ret];
  }
};

} // namespace wavelet_matrix_2d_impl

using wavelet_matrix_2d_impl::wavelet_matrix_2d;

#include <iostream>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, k;
  std::cin >> n >> k;
  std::vector<std::pair<int, int>> a(n * n);
  for (int i = 0; i != n; i += 1) {
    for (int j = 0; j != n; j += 1) {
      a[i * n + j].first = j;
      std::cin >> a[i * n + j].second;
    }
  }

  const wavelet_matrix_2d wm(a);

  int ans = 2e9;
  for (int i = 0; i <= n - k; i += 1) {
    for (int j = 0; j <= n - k; j += 1) {
      ans = std::min<int>(
          ans, wm.quantile(i * n, (i + k) * n, j, j + k, (k * k - 1) / 2));
    }
  }

  std::cout << ans << "\n";

  return 0;
}

Submission Info

Compile Error

./Main.cpp: In member function ‘wavelet_matrix_2d_impl::u32 wavelet_matrix_2d_impl::bit_vector::rank(wavelet_matrix_2d_impl::u32) const’:
./Main.cpp:78:75: warning: suggest parentheses around ‘-’ in operand of ‘&’ [-Wparentheses]
   78 |     return node.sum - popcount(node.bit & (static_cast<u32>(1) << i % 32) - 1);
      |                                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

Judge Result