結果

問題 No.3207 Digital Font
コンテスト
ユーザー cho435
提出日時 2026-03-15 12:43:10
言語 C++23(gnu拡張)
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 679 ms / 3,000 ms
コード長 6,248 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 8,901 ms
コンパイル使用メモリ 404,352 KB
実行使用メモリ 22,560 KB
最終ジャッジ日時 2026-03-15 12:43:40
合計ジャッジ時間 22,462 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;
}

// Bit Vector (for 64-bit non-negative integer)
struct bit_vector {
	// block: bit vector
	// count: the number of 1 within each block
	unsigned int n, zeros;
	vector<unsigned long long> block;
	vector<unsigned int> count;

	// constructor
	bit_vector() {};
	bit_vector(const unsigned int num)
		: n(num),
		  block(((num + 1) >> 6) + 1, 0),
		  count(((num + 1) >> 6) + 1, 0) {};

	// set val(0 or 1) onto i-th bit, get i-th bit of val(0 or 1)
	void set(const unsigned int i, const unsigned long long val = 1LL) {
		assert((i >> 6) < block.size());
		block[i >> 6] |= (val << (i & 63));
	}
	unsigned int get(const unsigned int i) const {
		assert((i >> 6) < block.size());
		return (unsigned int)(block[i >> 6] >> (i & 63)) & 1;
	}
	void build() {
		for (unsigned int i = 1; i < block.size(); i++) {
			count[i] = count[i - 1] + __builtin_popcountll(block[i - 1]);
		}
		zeros = rank0(n);
	}

	// the number of 1 in [0, i)
	unsigned int rank1(const unsigned int i) const {
		assert((i >> 6) < count.size());
		assert((i >> 6) < block.size());
		return count[i >> 6] + __builtin_popcountll(
								   block[i >> 6] & ((1ULL << (i & 63)) - 1ULL));
	}
	// the number of 1 in [i, j)
	unsigned int rank1(const unsigned int i, const unsigned int j) const {
		return rank1(j) - rank1(i);
	}
	// the number of 0 in [0, i)
	unsigned int rank0(const unsigned int i) const {
		return i - rank1(i);
	}
	// the number of 0 in [i, j)
	unsigned int rank0(const unsigned int i, const unsigned int j) const {
		return rank0(j) - rank0(i);
	}
	// the number of 0 in [0, n)
	unsigned int rank0() const {
		return zeros;
	}
};

template <typename T> struct wavelet_matrix {
	int n, height;
	vector<bit_vector> bv;
	wavelet_matrix() {};
	wavelet_matrix(const vector<T>& v) : n(v.size()), height(0) {
		if (n == 0) return;
		T mv = *max_element(v.begin(), v.end());
		for (height = 1; mv != 0; mv >>= 1) height++;
		vector<int> left(n), right(n), ord(n);
		iota(ord.begin(), ord.end(), 0);
		bv.assign(height, bit_vector(n));
		for (int h = height - 1; h >= 0; --h) {
			int l = 0, r = 0;
			for (int i = 0; i < n; ++i) {
				if ((v[ord[i]] >> h) & 1) {
					bv[h].set(i);
					right[r++] = ord[i];
				} else {
					left[l++] = ord[i];
				}
			}
			bv[h].build();
			ord.swap(left);
			for (int i = 0; i < r; ++i) ord[i + l] = right[i];
		}
	}
	int size() const {
		return height;
	}

	template <typename UPD>
	void add(int i, const T& y, const UPD& upd) {
		for (int h = height - 1; h >= 0; --h) {
			int i0 = bv[h].rank0(i);
			if ((y >> h) & 1) {
				i += bv[h].rank0() - i0;
			} else {
				i = i0;
			}
			upd(h, i);
		}
	}

	// count "i" s.t. v[i] \in [lower, upper), i \in [l, r)
	template <typename QUE>
	void rectangle_sum(int l, int r, const T& upper, const QUE& que) {
		assert(0 <= l && l <= r && r <= n);
		for (int h = height - 1; h >= 0; --h) {
			int l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
			if ((upper >> h) & 1) {
				l += bv[h].rank0() - l0;
				r += bv[h].rank0() - r0;
				que(h, l0, r0);
			} else {
				l = l0;
				r = r0;
			}
		}
	}

	template <typename ADD, typename DEL>
	void rectangle_sum(int l,
					   int r,
					   const T& lower,
					   const T& upper,
					   const ADD& add,
					   const DEL& del) {
		assert(l <= r && lower <= upper);
		rectangle_sum(l, r, upper, add);
		rectangle_sum(l, r, lower, del);
	}
};

using mint = atcoder::modint998244353;

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;
	int N;
	cin >> N;
	vector<array<int, 3>> v1, v2;
	rep(lp, 0, N) {
		int i, j, x;
		cin >> i >> j >> x;
		i--, j--;
		// seg1.set(i, j, MD1pw[i] * MD2pw[j] * x);
		v1.push_back({i, j, (MD1pw[i] * MD2pw[j] * x).val()});
		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);
		v2.push_back({ri, rj, (MD1pw[ri] * MD2pw[rj] * rx).val()});
	}
	sort(all(v1));
	sort(all(v2));

	wavelet_matrix<int> w1, w2;
	{
		vector<int> a1(N), a2(N);
		rep(i, 0, N) {
			a1[i] = v1[i][1];
			a2[i] = v2[i][1];
		}
		w1 = wavelet_matrix(a1);
		w2 = wavelet_matrix(a2);
	}

	vector ft1(w1.size(), atcoder::fenwick_tree<mint>(N)),
		ft2(w2.size(), atcoder::fenwick_tree<mint>(N));

	int n_q1 = 0;
	mint ad = 0;
	auto upd_q = [&](int h, int i) {
		if (n_q1) ft1[h].add(i, ad);
		else ft2[h].add(i, ad);
	};

	mint val = 0;
	auto add_q = [&](int h, int l, int r) {
		if (n_q1) val += ft1[h].sum(l, r);
		else val += ft2[h].sum(l, r);
	};
	auto del_q = [&](int h, int l, int r) {
		if (n_q1) val -= ft1[h].sum(l, r);
		else val -= ft2[h].sum(l, r);
	};

	n_q1 = 0;
	rep(i, 0, N) {
		ad = v1[i][2];
		w1.add(i, v1[i][1], upd_q);
	}

	n_q1 = 1;
	rep(i, 0, N) {
		ad = v2[i][2];
		w2.add(i, v2[i][1], upd_q);
	}
	int Q;
	cin >> Q;
	rep(Qi, 0, Q) {
		int l, d, r, u;
		cin >> l >> d >> r >> u;
		l--, d--;
		mint a1 = 0, a2 = 0;
		int l1 = lower_bound(all(v1), array<int, 3>{l, -1, -1}) - v1.begin();
		int r1 = lower_bound(all(v1), array<int, 3>{r, -1, -1}) - v1.begin();
		val = 0;
		n_q1 = 0;
		w1.rectangle_sum(l1, r1, d, u, add_q, del_q);
		a1 = val / (MD1pw[l] * MD2pw[d]);

		// auto v1 = seg1.prod(l, r, d, u);
		// v1 /= MD1pw[l] * MD2pw[d];
		int l2 =
			lower_bound(all(v2), array<int, 3>{H - l, -1, -1}) - v2.begin();
		int r2 =
			lower_bound(all(v2), array<int, 3>{H - r, -1, -1}) - v2.begin();

		val = 0;
		n_q1 = 1;
		w2.rectangle_sum(r2, l2, W - u, W - d, add_q, del_q);
		a2 = val / (MD1pw[H - r] * MD2pw[W - u]);
		// auto v2 = seg2.prod(H - r, H - l, W - u, W - d);
		// v2 /= MD1pw[H - r] * MD2pw[W - u];
		if (a1 == a2) cout << "Yes\n";
		else cout << "No\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(15);
	int t = 1;
	// cin >> t;
	while (t--) solve();
}
0