結果

問題 No.3207 Digital Font
コンテスト
ユーザー zawakasu
提出日時 2025-07-21 17:08:27
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 541 ms / 3,000 ms
コード長 4,033 bytes
コンパイル時間 3,840 ms
コンパイル使用メモリ 310,868 KB
実行使用メモリ 18,156 KB
最終ジャッジ日時 2025-07-21 17:08:48
合計ジャッジ時間 20,037 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep2(i, n) for (ll i = 0; i < (n); i++) 
#define rep3(i, a, b) for(ll i = a; i < (b); i++)
#define overload(a, b, c, d, ...) d
#define rep(...) overload(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define all(a) begin(a), end(a)
#define sz(a) ssize(a)
bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }

template <class Z, class T>
struct PointRS {
    Z x, y;
    T w;
};
template <class Z>
struct RectRS {
    Z l, d, r, u;
    // [l, r)x[d, u)
};
template <class Z, class T, auto op, auto e, auto inv>
vector<T> RectangleSum(vector<PointRS<Z, T>> p, vector<RectRS<Z>> q) {
    int n = ssize(p), m = ssize(q);
    vector<Z> xs(n);
    rep(i, n) xs[i] = p[i].x;
    ranges::sort(xs);
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    auto comp = [&](int x) {
        return ranges::lower_bound(xs, x) - xs.begin();
    };
    ranges::sort(p, [&](const auto& l, const auto& r) { return l.y < r.y; });
    vector<pair<Z, int>> event(2*m);
    rep(i, m) {
        event[i] = {q[i].d, i};
        event[i + m] = {q[i].u, i + m};
    } 
    ranges::sort(event);
    vector<T> fen(xs.size() + 1, e()), res(m);
    auto prod = [&](int l, int r) {
        T L = e(), R = e();
        for ( ; r ; r -= r & -r) R = op(R, fen[r]);
        for ( ; l ; l -= l & -l) L = op(L, fen[l]);
        return op(inv(L), R);
    };
    for (int i = 0 ; auto [cur, j] : event) {
        for ( ; i < n and p[i].y < cur ; i++) 
            for (int x = comp(p[i].x) + 1 ; x < ssize(fen) ; x += x & -x) 
                fen[x] = op(fen[x], p[i].w);
        T sum = prod(comp(q[j%m].l), comp(q[j%m].r));
        if (j < m) res[j] = op(res[j], inv(sum));
        else res[j-m] = op(res[j-m], sum);
    }
    return res;
}
/*
 * 1. x座標は座圧する
 * 2. sum [l, r)x[d, u)をsum [-inf, r)x[d, u) - sum [-inf, l)x[d, u)に言い換える
 * 3. y軸に関して平面走査する
 * 4. fenwick treeで[-inf, x)x[d, u)を計算する
 *
 * auto op = plus<T>{};
 * auto e = []() { return 0LL; };
 * auto inv = negate<T>{};
 */

const long long M = 998244353;
const long long B1 = 112233;
const long long B2 = 332211;
long long mod_inv(long long v) {
    long long res = 1, e = M - 2;
    while (e) {
        if (e & 1) res = (res * v) % M;
        v = (v * v) % M;
        e >>= 1;
    }
    return res;
}
int main() {
    int H, W, N;
    cin >> H >> W >> N;
    vector<long long> pow1(W, 1), pow2(H, 1);
    for (int i = 1 ; i < W ; i++) pow1[i] = (pow1[i - 1] * B1) % M;
    for (int i = 1 ; i < H ; i++) pow2[i] = (pow2[i - 1] * B2) % M;
    auto point_hash = [&](int x, int y, int v) {
        assert(0 <= x and x < W);
        assert(0 <= y and y < H);
        return (((pow1[x] * pow2[y]) % M) * v) % M;
    };
    vector<PointRS<int, long long>> a(N), b(N);
    for (int i = 0 ; i < N ; i++) {
        int x, y, v;
        cin >> y >> x >> v;
        x--; y--;
        a[i] = {x, y, point_hash(x, y, v)};
        x = W - x - 1;
        y = H - y - 1;
        v = (v == 6 ? 9 : (v == 9 ? 6 : v));
        b[i] = {x, y, point_hash(x, y, v)};
    }
    int Q;
    cin >> Q;
    vector<RectRS<int>> ra(Q), rb(Q);
    for (int i = 0 ; i < Q ; i++) {
        int l, d, r, u;
        cin >> d >> l >> u >> r;
        l--; d--;
        ra[i] = {l, d, r, u};
        rb[i] = {W - r, H - u, W - l, H - d};
    }
    auto op = [&](long long l, long long r) { return (l + r) % M; };
    auto e = [&]() { return 0LL; };
    auto inv = [&](long long v) { return v ? M - v : v; };
    auto Solver = RectangleSum<int, long long, op, e, inv>;
    auto A = Solver(a, ra), B = Solver(b, rb);
    for (int i = 0 ; i < Q ; i++) {
        long long ha = A[i], ia = (mod_inv(pow1[ra[i].l]) * mod_inv(pow2[ra[i].d])) % M;
        long long hb = B[i], ib = (mod_inv(pow1[rb[i].l]) * mod_inv(pow2[rb[i].d])) % M;
        ha = (ha * ia) % M;
        hb = (hb * ib) % M;
        std::cout << (ha == hb ? "Yes\n" : "No\n");
    }
}
0