結果

問題 No.3207 Digital Font
ユーザー cho435
提出日時 2025-07-24 18:11:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,127 bytes
コンパイル時間 4,218 ms
コンパイル使用メモリ 262,044 KB
実行使用メモリ 241,056 KB
最終ジャッジ日時 2025-07-24 18:11:15
合計ジャッジ時間 10,277 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)

template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

struct io_setup {
	io_setup() {
		ios::sync_with_stdio(false);
		std::cin.tie(nullptr);
		cout << fixed << setprecision(15);
	}
} io_setup;

namespace cho {

template <class S, auto op, auto e> struct dynamic_segtree_2D {
	size_t H, W;
	std::map<size_t, S> seg;
	dynamic_segtree_2D() {};
	dynamic_segtree_2D(size_t h, size_t w) {
		H = W = 1;
		while (H < h) H <<= 1;
		while (W < w) W <<= 1;
	}
	size_t id(size_t h, size_t w) const {
		return h * 2 * W + w;
	}
	S _inner_get(size_t h, size_t w) const {
		auto itr = seg.find(id(h, w));
		if (itr == seg.end()) return e();
		return itr->second;
	}
	void set(size_t h, size_t w, const S& x) {
		assert(h < H && w < W);
		h += H, w += W;
		seg[id(h, w)] = x;
		for (size_t i = h >> 1; i; i >>= 1) {
			seg[id(i, w)] = op(_inner_get(2 * i, w), _inner_get(2 * i + 1, w));
		}
		for (; h; h >>= 1) {
			for (size_t j = w >> 1; j; j >>= 1) {
				seg[id(h, j)] =
					op(_inner_get(h, 2 * j), _inner_get(h, 2 * j + 1));
			}
		}
	}
	S get(size_t h, size_t w) const {
		return _inner_get(h + H, w + W);
	}
	S _inner_prod(size_t h, size_t w1, size_t w2) const {
		S res = e();
		for (; w1 < w2; w1 >>= 1, w2 >>= 1) {
			if (w1 & 1) res = op(res, _inner_get(h, w1)), w1++;
			if (w2 & 1) --w2, res = op(res, _inner_get(h, w2));
		}
		return res;
	}
	S prod(size_t h1, size_t w1, size_t h2, size_t w2) const {
		assert(h1 <= h2 && h2 <= H);
		assert(w1 <= w2 && w2 <= W);
		if (h1 >= h2 || w1 >= w2) return e();
		S res = e();
		h1 += H, h2 += H, w1 += W, w2 += W;
		for (; h1 < h2; h1 >>= 1, h2 >>= 1) {
			if (h1 & 1) res = op(res, _inner_prod(h1, w1, w2)), h1++;
			if (h2 & 1) --h2, res = op(res, _inner_prod(h2, w1, w2));
		}
		return res;
	}
};

}  // namespace cho

using mint = atcoder::modint998244353;
mint op(mint a, mint b) {
	return a + b;
}
mint e() {
	return 0;
}

using segtree2D = cho::dynamic_segtree_2D<mint, op, e>;

void solve() {
	const mint MD1 = 10009;
	const mint MD2 = 10007;
	vector<mint> MD1pw(2e5, 1), MD2pw(2e5, 1);
	rep(i, 1, 2e5) {
		MD1pw[i] = MD1pw[i - 1] * MD1;
		MD2pw[i] = MD2pw[i - 1] * MD2;
	}

	int H, W;
	cin >> H >> W;
	segtree2D seg1(H, W), seg2(H, W);
	int N;
	cin >> N;
	rep(lp, 0, N) {
		int i, j, x;
		cin >> i >> j >> x;
		i--, j--;
		seg1.set(i, j, MD1pw[i] * MD2pw[j] * x);
		int ri = H - 1 - i, rj = W - 1 - j;
		int rx = x;
		if (x == 6) rx = 9;
		if (x == 9) rx = 6;
		seg2.set(ri, rj, MD1pw[ri] * MD2pw[rj] * rx);
	}
	int Q;
	cin >> Q;
	rep(Qi, 0, Q) {
		int l, d, r, u;
		cin >> l >> d >> r >> u;
		l--, d--;
		auto v1 = seg1.prod(l, d, r, u);
		v1 /= MD1pw[l] * MD2pw[u];
		auto v2 = seg2.prod(H - r, W - u, H - l, W - d);
		v2 /= MD1pw[H - r] * MD2pw[W - d];
		if (v1 == v2) cout << "Yes\n";
		else cout << "No\n";
	}
}

int main() {
	int t = 1;
	// cin >> t;
	while (t--) solve();
}
0