結果

問題 No.3207 Digital Font
ユーザー cho435
提出日時 2025-07-26 01:44:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 7,261 bytes
コンパイル時間 6,176 ms
コンパイル使用メモリ 273,548 KB
実行使用メモリ 187,556 KB
最終ジャッジ日時 2025-07-26 01:45:06
合計ジャッジ時間 13,796 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 lorent {

template <class S, S (*op)(S, S), S (*e)()> class dynamic_segtree {
   public:
	dynamic_segtree() = default;
	dynamic_segtree(size_t n) : n(n), root(nullptr) {
	}

	void set(size_t p, S x) {
		assert(p < n);
		set(root, 0, n, p, x);
	}

	S get(size_t p) const {
		assert(p < n);
		return get(root, 0, n, p);
	}

	S prod(size_t l, size_t r) const {
		assert(l <= r && r <= n);
		return prod(root, 0, n, l, r);
	}

	S all_prod() const {
		return root ? root->product : e();
	}

	void reset(size_t l, size_t r) {
		assert(l <= r && r <= n);
		return reset(root, 0, n, l, r);
	}

	template <bool (*f)(S)> size_t max_right(size_t l) const {
		return max_right(l, [](S x) {
			return f(x);
		});
	}

	template <class F> size_t max_right(size_t l, const F& f) const {
		assert(l <= n);
		S product = e();
		assert(f(product));
		return max_right(root, 0, n, l, f, product);
	}

	template <bool (*f)(S)> size_t min_left(size_t r) const {
		return min_left(r, [](S x) {
			return f(x);
		});
	}

	template <class F> size_t min_left(size_t r, const F& f) const {
		assert(r <= n);
		S product = e();
		assert(f(product));
		return min_left(root, 0, n, r, f, product);
	}

   private:
	struct node;
	using node_ptr = std::unique_ptr<node>;

	struct node {
		size_t index;
		S value, product;
		node_ptr left, right;

		node(size_t index, S value)
			: index(index),
			  value(value),
			  product(value),
			  left(nullptr),
			  right(nullptr) {
		}

		void update() {
			product = op(op(left ? left->product : e(), value),
						 right ? right->product : e());
		}
	};

	const size_t n;
	node_ptr root;

	void set(node_ptr& t, size_t a, size_t b, size_t p, S x) const {
		if (!t) {
			t = std::make_unique<node>(p, x);
			return;
		}
		if (t->index == p) {
			t->value = x;
			t->update();
			return;
		}
		size_t c = (a + b) >> 1;
		if (p < c) {
			if (t->index < p) std::swap(t->index, p), std::swap(t->value, x);
			set(t->left, a, c, p, x);
		} else {
			if (p < t->index) std::swap(p, t->index), std::swap(x, t->value);
			set(t->right, c, b, p, x);
		}
		t->update();
	}

	S get(const node_ptr& t, size_t a, size_t b, size_t p) const {
		if (!t) return e();
		if (t->index == p) return t->value;
		size_t c = (a + b) >> 1;
		if (p < c) return get(t->left, a, c, p);
		else return get(t->right, c, b, p);
	}

	S prod(const node_ptr& t, size_t a, size_t b, size_t l, size_t r) const {
		if (!t || b <= l || r <= a) return e();
		if (l <= a && b <= r) return t->product;
		size_t c = (a + b) >> 1;
		S result = prod(t->left, a, c, l, r);
		if (l <= t->index && t->index < r) result = op(result, t->value);
		return op(result, prod(t->right, c, b, l, r));
	}

	void reset(node_ptr& t, size_t a, size_t b, size_t l, size_t r) const {
		if (!t || b <= l || r <= a) return;
		if (l <= a && b <= r) {
			t.reset();
			return;
		}
		size_t c = (a + b) >> 1;
		reset(t->left, a, c, l, r);
		reset(t->right, c, b, l, r);
		t->update();
	}

	template <class F>
	size_t max_right(const node_ptr& t,
					 size_t a,
					 size_t b,
					 size_t l,
					 const F& f,
					 S& product) const {
		if (!t || b <= l) return n;
		if (f(op(product, t->product))) {
			product = op(product, t->product);
			return n;
		}
		size_t c = (a + b) >> 1;
		size_t result = max_right(t->left, a, c, l, f, product);
		if (result != n) return result;
		if (l <= t->index) {
			product = op(product, t->value);
			if (!f(product)) return t->index;
		}
		return max_right(t->right, c, b, l, f, product);
	}

	template <class F>
	size_t min_left(const node_ptr& t,
					size_t a,
					size_t b,
					size_t r,
					const F& f,
					S& product) const {
		if (!t || r <= a) return 0;
		if (f(op(t->product, product))) {
			product = op(t->product, product);
			return 0;
		}
		size_t c = (a + b) >> 1;
		size_t result = min_left(t->right, c, b, r, f, product);
		if (result != 0) return result;
		if (t->index < r) {
			product = op(t->value, product);
			if (!f(product)) return t->index + 1;
		}
		return min_left(t->left, a, c, r, f, product);
	}
};

}  // namespace lorent

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 {
		lorent::dynamic_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