結果

問題 No.3207 Digital Font
コンテスト
ユーザー cho435
提出日時 2025-07-18 23:12:25
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2,407 ms / 3,000 ms
コード長 5,130 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,769 ms
コンパイル使用メモリ 284,472 KB
実行使用メモリ 142,288 KB
最終ジャッジ日時 2025-07-18 23:13:09
合計ジャッジ時間 42,364 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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;

template <typename T>
struct BinaryIndexedTree {
	vector<T> data;

	BinaryIndexedTree(int sz) {
		data.assign(++sz, 0);
	}

	T sum(int k) {
		T ret = 0;
		for (++k; k > 0; k -= k & -k) ret += data[k];
		return (ret);
	}

	void add(int k, T x) {
		for (++k; k < data.size(); k += k & -k) data[k] += x;
	}
};

template <typename structure_t, typename get_t, typename update_t>
struct SegmentTree2DCompressed {
	using merge_f = function<get_t(get_t, get_t)>;
	using range_get_f = function<get_t(structure_t&, int, int)>;
	using update_f = function<void(structure_t&, int, update_t)>;

	int sz;
	vector<structure_t> seg;
	const merge_f f;
	const range_get_f g;
	const update_f h;
	const get_t identity;
	vector<vector<int>> LL, RR;
	vector<vector<int>> beet;

	SegmentTree2DCompressed(int n,
							const merge_f& f,
							const range_get_f& g,
							const update_f& h,
							const get_t& identity)
		: f(f), g(g), h(h), identity(identity) {
		sz = 1;
		while (sz < n) sz <<= 1;
		beet.resize(2 * sz);
		LL.resize(2 * sz);
		RR.resize(2 * sz);
	}

	void update(int a, int x, update_t z, int k, int l, int r) {
		if (r <= a || a + 1 <= l) return;
		if (a <= l && r <= a + 1) return h(seg[k], x, z);
		update(a, LL[k][x], z, 2 * k + 0, l, (l + r) >> 1);
		update(a, RR[k][x], z, 2 * k + 1, (l + r) >> 1, r);
		return h(seg[k], x, z);
	}

	void update(int x, int y, update_t z) {
		y = lower_bound(begin(beet[1]), end(beet[1]), y) - begin(beet[1]);
		return update(x, y, z, 1, 0, sz);
	}

	get_t query(int a, int b, int x, int y, int k, int l, int r) {
		if (a >= r || b <= l) return identity;
		if (a <= l && r <= b) return g(seg[k], x, y);
		return f(query(a, b, LL[k][x], LL[k][y], 2 * k + 0, l, (l + r) >> 1),
				 query(a, b, RR[k][x], RR[k][y], 2 * k + 1, (l + r) >> 1, r));
	}

	get_t query(int a, int b, int x, int y) {
		x = lower_bound(begin(beet[1]), end(beet[1]), x) - begin(beet[1]);
		y = lower_bound(begin(beet[1]), end(beet[1]), y) - begin(beet[1]);
		return query(a, b, x, y, 1, 0, sz);
	}

	void build() {
		for (int k = (int)beet.size() - 1; k >= sz; k--) {
			sort(begin(beet[k]), end(beet[k]));
			beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k]));
		}
		for (int k = sz - 1; k > 0; k--) {
			beet[k].resize(beet[2 * k + 0].size() + beet[2 * k + 1].size());
			merge(begin(beet[2 * k + 0]), end(beet[2 * k + 0]),
				  begin(beet[2 * k + 1]), end(beet[2 * k + 1]), begin(beet[k]));
			beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k]));
			LL[k].resize(beet[k].size() + 1);
			RR[k].resize(beet[k].size() + 1);
			int tail1 = 0, tail2 = 0;
			for (int i = 0; i < beet[k].size(); i++) {
				while (tail1 < beet[2 * k + 0].size() &&
					   beet[2 * k + 0][tail1] < beet[k][i])
					++tail1;
				while (tail2 < beet[2 * k + 1].size() &&
					   beet[2 * k + 1][tail2] < beet[k][i])
					++tail2;
				LL[k][i] = tail1, RR[k][i] = tail2;
			}
			LL[k][beet[k].size()] = (int)beet[2 * k + 0].size();
			RR[k][beet[k].size()] = (int)beet[2 * k + 1].size();
		}
		for (int k = 0; k < beet.size(); k++) {
			seg.emplace_back(structure_t(beet[k].size()));
		}
	}

	void preupdate(int x, int y) {
		beet[x + sz].push_back(y);
	}
};

using mint = atcoder::modint998244353;

void solve() {
	const mint MD1 = 10009;
	const mint MD2 = 10007;
	using BIT = BinaryIndexedTree<mint>;
	auto f = [](mint x, mint y) {
		return x + y;
	};
	auto g = [](BIT& k, int x, int y) {
		return k.sum(y - 1) - k.sum(x - 1);
	};
	auto h = [](BIT& k, int x, mint y) {
		k.add(x, y);
	};

	SegmentTree2DCompressed<BIT, mint, mint> seg1(100002, f, g, h, 0);
	SegmentTree2DCompressed<BIT, mint, mint> seg2(100002, f, g, h, 0);

	int H, W;
	cin >> H >> W;
	int N;
	cin >> N;
	vector<tuple<int, int, mint>> vp1, vp2;
	rep(lp, 0, N) {
		int i, j, x;
		cin >> i >> j >> x;
		i--, j--;
		vp1.push_back({i, j, MD1.pow(i) * MD2.pow(j) * x});
		int ri = H - 1 - i, rj = W - 1 - j;
		int rx = x;
		if (x == 6) rx = 9;
		if (x == 9) rx = 6;
		vp2.push_back({ri, rj, MD1.pow(ri) * MD2.pow(rj) * rx});
	}
	for (auto [i, j, k] : vp1) {
		seg1.preupdate(i, j);
	}
	for (auto [i, j, k] : vp2) {
		seg2.preupdate(i, j);
	}
	seg1.build();
	seg2.build();
	for (auto [i, j, k] : vp1) {
		seg1.update(i, j, k);
	}
	for (auto [i, j, k] : vp2) {
		seg2.update(i, j, k);
	}
	int Q;
	cin >> Q;
	rep(Qi, 0, Q) {
		int l, d, r, u;
		cin >> l >> d >> r >> u;
		l--, d--;
		auto v1 = seg1.query(l, r, u, d);
		v1 /= MD1.pow(l) * MD2.pow(u);
		auto v2 = seg2.query(H - r, H - l, W - d, W - u);
		v2 /= MD1.pow(H - r) * MD2.pow(W - d);
		if (v1 == v2) cout << "Yes\n";
		else cout << "No\n";
	}
}

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