結果

問題 No.3207 Digital Font
ユーザー lmorinn
提出日時 2025-07-22 18:16:22
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 748 ms / 3,000 ms
コード長 7,412 bytes
コンパイル時間 7,300 ms
コンパイル使用メモリ 313,300 KB
実行使用メモリ 77,740 KB
最終ジャッジ日時 2025-07-22 18:16:46
合計ジャッジ時間 20,700 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template <class T>
struct BitVector {
  unsigned sz;
  unsigned blocksize;
  vector<unsigned long long> bit;
  vector<unsigned> sum;
  vector<T> srsum;

  BitVector() {}

  BitVector(unsigned siz) {
    sz = siz;
    blocksize = (sz + 63) >> 6;
    bit.assign(blocksize, 0ULL);
    sum.assign(blocksize, 0U);
    srsum.assign(sz, 0);
  }

  inline void set(int k) { bit[k >> 6] |= 1ULL << (k & 63ULL); }

  inline void build() {
    sum[0] = 0ULL;
    for (int i = 1; i < blocksize; i++) {
      sum[i] = sum[i - 1] + __builtin_popcountll(bit[i - 1]);
    }
  }

  inline bool access(unsigned k) {
    return (bool((bit[k >> 6] >> (k & 63)) & 1));
  }

  inline int rank(int k) {
    return (sum[k >> 6] + __builtin_popcountll(bit[k >> 6] & ((1ULL << (k & 63)) - 1)));
  }

  inline void srsum_set(vector<T> &v) {
    for (int i = 0; i < sz - 1; i++) {
      srsum[i + 1] = srsum[i] + v[i];
    }
  }

  inline T rank_srsum(int l, int r) {
    return srsum[r] - srsum[l];
  }

  inline T rank_srsum(int r) {
    return srsum[r];
  }
};

template <class T, class S>
class WaveletMatrix {
 private:
  unsigned n;
  unsigned bitsize;
  vector<BitVector<S>> b;
  vector<unsigned> zero;
  vector<T> cmp;
  T MI, MA;

  inline unsigned compress(const T &x) {
    return lower_bound(cmp.begin(), cmp.end(), x) - begin(cmp);
  }

 public:
  // コンストラクタ
  WaveletMatrix() {}
  WaveletMatrix(vector<T> v) {
    MI = numeric_limits<T>::min();
    MA = numeric_limits<T>::max();
    n = v.size();
    cmp = v;
    sort(cmp.begin(), cmp.end());
    cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
    vector<T> tmp(n);
    vector<T> tmpc(n);
    vector<T> compressed(n);
    for (unsigned i = 0; i < n; i++) {
      compressed[i] = distance(cmp.begin(), lower_bound(cmp.begin(), cmp.end(), v[i]));
    }
    bitsize = bit_width(cmp.size());
    b.resize(bitsize + 1);
    zero.resize(bitsize, 0);
    int cur = 0;
    for (unsigned i = 0; i < bitsize; i++) {
      b[i] = BitVector<T>(n + 1);
      b[i].srsum_set(v);
      cur = 0;
      for (unsigned j = 0; j < n; j++) {
        if (compressed[j] & (1U << (bitsize - i - 1))) {
          b[i].set(j);
        } else {
          zero[i]++;
          tmpc[cur] = compressed[j];
          tmp[cur] = v[j];
          cur++;
        }
      }
      b[i].build();
      for (int j = 0; j < n; j++) {
        if (compressed[j] & (1U << (bitsize - i - 1))) {
          tmpc[cur] = compressed[j];
          tmp[cur] = v[j];
          cur++;
        }
      }
      swap(tmpc, compressed);
      swap(tmp, v);
    }
    b[bitsize] = BitVector<T>(n + 1);
    b[bitsize].srsum_set(v);
  }

  WaveletMatrix(vector<T> v, vector<S> w) {
    MI = numeric_limits<T>::min();
    MA = numeric_limits<T>::max();
    n = v.size();
    cmp = v;
    sort(cmp.begin(), cmp.end());
    cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
    vector<S> tmp(n);
    vector<T> tmpc(n);
    vector<T> compressed(n);
    for (unsigned i = 0; i < n; i++) {
      compressed[i] = distance(cmp.begin(), lower_bound(cmp.begin(), cmp.end(), v[i]));
    }
    bitsize = bit_width(cmp.size());
    b.resize(bitsize + 1);
    zero.resize(bitsize, 0);
    int cur = 0;
    for (unsigned i = 0; i < bitsize; i++) {
      b[i] = BitVector<S>(n + 1);
      b[i].srsum_set(w);
      cur = 0;
      for (unsigned j = 0; j < n; j++) {
        if (compressed[j] & (1U << (bitsize - i - 1))) {
          b[i].set(j);
        } else {
          zero[i]++;
          tmpc[cur] = compressed[j];
          tmp[cur] = w[j];
          cur++;
        }
      }
      b[i].build();
      for (int j = 0; j < n; j++) {
        if (compressed[j] & (1U << (bitsize - i - 1))) {
          tmpc[cur] = compressed[j];
          tmp[cur] = w[j];
          cur++;
        }
      }
      swap(tmpc, compressed);
      swap(tmp, w);
    }
    b[bitsize] = BitVector<S>(n + 1);
    b[bitsize].srsum_set(w);
  }

  // v[l,r) の中で[mink,maxk)に入る値の総和を返す
  S range_sum(int vl, int vr, T mink, T maxk) {
    int D = compress(mink);
    int U = compress(maxk);
    S res = 0;
    auto dfs = [&](auto &rec, int d, int L, int R, int A, int B) -> void {
      if (U <= A or B <= D) return;
      if (D <= A and B <= U) {
        res = res + b[d].rank_srsum(L, R);
        return;
      }
      if (d == bitsize) {
        if (D <= A and A < U) {
          res = res + b[d].rank_srsum(L, R);
        }
        return;
      }
      int C = (A + B) / 2;
      int rank0_l = L - b[d].rank(L);
      int rank0_r = R - b[d].rank(R);
      int rank1_l = b[d].rank(L) + zero[d];
      int rank1_r = b[d].rank(R) + zero[d];
      rec(rec, d + 1, rank0_l, rank0_r, A, C);
      rec(rec, d + 1, rank1_l, rank1_r, C, B);
    };
    dfs(dfs, 0, vl, vr, 0, 1 << bitsize);
    return res;
  }
};

template <class T, class S>
class RectangleSum {
 private:
  WaveletMatrix<T, S> wm;
  vector<T> px;

 public:
  RectangleSum() {}
  RectangleSum(vector<T> x, vector<T> y, vector<S> w) {
    int n = int(x.size());
    vector<tuple<T, T, S>> v(n);
    for (int i = 0; i < n; i++) v[i] = {x[i], y[i], w[i]};
    sort(v.begin(), v.end(), [](const auto &a, const auto &b) {
      return get<0>(a) < get<0>(b);
    });
    px.resize(n);
    for (int i = 0; i < n; i++) {
      px[i] = get<0>(v[i]);
      y[i] = get<1>(v[i]);
      w[i] = get<2>(v[i]);
    }
    wm = WaveletMatrix<T, S>(y, w);
  }

  S rectangle_sum(T xl, T xr, T yl, T yr) {
    int l = distance(px.begin(), lower_bound(px.begin(), px.end(), xl));
    int r = distance(px.begin(), lower_bound(px.begin(), px.end(), xr));
    return wm.range_sum(l, r, yl, yr);
  }
};

__int128_t mod_pow(__int128_t a, long long n, long long m) {
  __int128_t res = 1;
  a %= m;
  while (n) {
    if (n & 1) res = (res * a) % m;
    a = (a * a) % m;
    n >>= 1;
  }
  return res;
}

constexpr long long mod = (1ll << 61) - 1;
constexpr long long base_y = 4567;
constexpr long long base_x = 6873;

vector<__int128_t> py, px;

__int128_t my_hash(long long x, long long y, long long c) {
  return ((py[y] * px[x] % mod) * c) % mod;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int h, w, n;
  cin >> h >> w >> n;
  py.resize(h + 1);
  px.resize(w + 1);
  py[0] = px[0] = 1;
  for (long long i = 1; i <= h; i++) py[i] = (py[i - 1] * base_y) % mod;
  for (long long i = 1; i <= w; i++) px[i] = (px[i - 1] * base_x) % mod;
  vector<int> x1(n), y1(n), x2(n), y2(n);
  vector<__int128_t> z1(n), z2(n);
  vector<int> flip = {0, 1, 2, 33, 44, 5, 9, 77, 8, 6};
  for (int i = 0; i < n; i++) {
    int x_, y_, c;
    cin >> y_ >> x_ >> c;
    x1[i] = x_;
    y1[i] = y_;
    z1[i] = my_hash(x_, y_, c);
    x2[i] = w - x_ + 1;
    y2[i] = h - y_ + 1;
    z2[i] = my_hash(x2[i], y2[i], flip[c]);
  }

  RectangleSum<int, __int128_t> w1(x1, y1, z1);
  RectangleSum<int, __int128_t> w2(x2, y2, z2);

  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    int ly, ry, lx, rx;
    cin >> ly >> lx >> ry >> rx;
    int ly2 = h - ry + 1;
    int ry2 = h - ly + 1;
    int lx2 = w - rx + 1;
    int rx2 = w - lx + 1;
    long long h1 = (((w1.rectangle_sum(lx, rx + 1, ly, ry + 1) % mod) * py[ly2]) % mod) * px[lx2] % mod;
    long long h2 = (((w2.rectangle_sum(lx2, rx2 + 1, ly2, ry2 + 1) % mod) * py[ly]) % mod) * px[lx] % mod;
    if (h1 == h2) {
      cout << "Yes\n";
    } else {
      cout << "No\n";
    }
  }
}
0