結果
問題 |
No.3207 Digital Font
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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"); } }