結果

問題 No.3207 Digital Font
ユーザー cho435
提出日時 2025-07-26 16:17:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 3,223 bytes
コンパイル時間 4,820 ms
コンパイル使用メモリ 272,768 KB
実行使用メモリ 813,964 KB
最終ジャッジ日時 2025-07-26 16:17:47
合計ジャッジ時間 8,669 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other MLE * 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;

#include <atcoder/segtree>

namespace cho {

template <class S, auto op, auto e> struct dynamic_segtree_2D {
	size_t H, W;
	dynamic_segtree_2D(size_t h, size_t w) : W(w) {
		H = 1;
		while (H < h) H <<= 1;
	};
	struct node;
	using node_ptr = std::unique_ptr<node>;
	struct node {
		atcoder::segtree<S, op, e> seg;
		node_ptr left, right;
		node(size_t w) : seg(w), left(nullptr), right(nullptr) {};
	};
	void set(size_t h, size_t w, const S& x) {
		_set(root, 0, H, h, w, x);
	}
	S get(size_t h, size_t w) const {
		return _get(root, 0, H, h, w);
	}
	S prod(size_t hl, size_t hr, size_t wl, size_t wr) const {
		return _prod(root, 0, H, hl, hr, wl, wr);
	}
	S all_prod() const {
		return root ? root->seg.all_prod() : e();
	}

	node_ptr root;
	void _set(node_ptr& t, size_t l, size_t r, size_t h, size_t w, const S& x) {
		if (!t) t = std::make_unique<node>(W);
		t->seg.set(w, op(t->seg.get(w), x));
		if (l + 1 == r) return;
		size_t md = (l + r) >> 1;
		if (h < md) _set(t->left, l, md, h, w, x);
		else _set(t->right, md, r, h, w, x);
	}
	S _get(const node_ptr& t, size_t l, size_t r, size_t h, size_t w) const {
		if (!t) return e();
		if (l + 1 == r) return t->seg.get(w);
		size_t md = (l + r) >> 1;
		if (h < md) return _get(t->left, l, md, h, w);
		return _get(t->right, md, r, h, w);
	}
	S _prod(const node_ptr& t,
			size_t l,
			size_t r,
			size_t hl,
			size_t hr,
			size_t wl,
			size_t wr) const {
		if (!t || r <= hl || hr <= l) return e();
		if (hl <= l && r <= hr) return t->seg.prod(wl, wr);
		size_t md = (l + r) >> 1;
		return op(_prod(t->left, l, md, hl, hr, wl, wr),
				  _prod(t->right, md, r, hl, hr, wl, wr));
	}
};

}  // 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, r, d, u);
		v1 /= MD1pw[l] * MD2pw[d];
		auto v2 = seg2.prod(H - r, H - l, W - u, W - d);
		v2 /= MD1pw[H - r] * MD2pw[W - u];
		if (v1 == v2) cout << "Yes\n";
		else cout << "No\n";
	}
}

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