結果

問題 No.3207 Digital Font
コンテスト
ユーザー lmorinn
提出日時 2025-07-16 14:34:52
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,456 ms / 3,000 ms
コード長 9,344 bytes
コンパイル時間 4,239 ms
コンパイル使用メモリ 314,556 KB
実行使用メモリ 42,504 KB
最終ジャッジ日時 2025-07-16 21:18:52
合計ジャッジ時間 39,199 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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);
    }
};

class Modint {
   private:
    static const long long m = (1ll << 61) - 1;
    long long value;

   public:
    Modint() {
        value = 0;
    }
    Modint(long long x) {
        value = x % m;
    }

    long long val() {
        return value;
    }

    long long mod() {
        return m;
    }

    Modint operator+(const Modint &b) {
        Modint ret(val() + b.value);
        return ret;
    }
};

bool operator==(Modint &a, Modint &b) {
    return a.val() == b.val();
}

Modint operator+(Modint &a, Modint &b) {
    Modint ret(a.val() + b.val());
    return ret;
}

Modint operator-(Modint &a, Modint &b) {
    Modint ret(a.val() + a.mod() - b.val());
    return ret;
}

Modint operator*(Modint &a, Modint &b) {
    long long res = (__int128_t(a.val()) * __int128_t(b.val())) % a.mod();
    return Modint(res);
}

__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;

Modint my_hash(long long x, long long y, long long c) {
    long long tmp = (((__int128_t(mod_pow(base_y, y, mod)) * __int128_t(mod_pow(base_x, x, mod))) % mod) * c) % mod;
    return Modint(tmp);
}

int main() {
    int h, w, n;
    cin >> h >> w >> n;
    vector<int> x1(n), y1(n), x2(n), y2(n);
    vector<Modint> 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, Modint> w1(x1, y1, z1);
    RectangleSum<int, Modint> 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;
        __int128_t h1 = w1.rectangle_sum(lx, rx + 1, ly, ry + 1).val();
        h1 *= mod_pow(mod_pow(base_y, ly, mod), mod - 2, mod);
        h1 %= mod;
        h1 *= mod_pow(mod_pow(base_x, lx, mod), mod - 2, mod);
        h1 %= mod;
        int ly2 = h - ry + 1;
        int ry2 = h - ly + 1;
        int lx2 = w - rx + 1;
        int rx2 = w - lx + 1;
        __int128_t h2 = w2.rectangle_sum(lx2, rx2 + 1, ly2, ry2 + 1).val();
        h2 *= mod_pow(mod_pow(base_y, ly2, mod), mod - 2, mod);
        h2 %= mod;
        h2 *= mod_pow(mod_pow(base_x, lx2, mod), mod - 2, mod);
        h2 %= mod;

        if (h1 == h2) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}
0