#1186067 (C++23) No.3709 Unknown Treasure

• 問題: No.3709 Unknown Treasure
• ユーザー: kwm_t
• 提出日時: 2026-09-11 21:30:07
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 61 ms / 2,000 ms
• コード長: 3,734 bytes
• コンパイル時間: 2,218 ms
• コンパイル使用メモリ: 339,524 KB
• 実行使用メモリ: 19,200 KB
• 最終ジャッジ日時: 2026-09-11 21:30:53
• 合計ジャッジ時間: 5,568 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 36

ソースコード

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; }
#ifndef KWM_T_UTILITY_IMOS_2D_HPP
#define KWM_T_UTILITY_IMOS_2D_HPP

#include <vector>
#include <cassert>

namespace kwm_t::utility {

/**
 * @brief 2次元いもす法（2D Difference Array / 2D Imos）
 *
 * 典型用途:
 *   - 長方形領域への一括加算
 *   - グリッドへの大量区間更新
 *   - 塗りつぶし・重なり数計算
 *
 * 計算量:
 *   - add: O(1)
 *   - build: O(HW)
 *   - get: O(1)
 *
 * @tparam T
 *   加算・減算が定義されている型
 *
 * 制約 / 注意:
 *   - add(x0, y0, x1, y1, val) は
 *       半開区間 [x0, x1) × [y0, y1)
 *     に val を加算する
 *   - 0-indexed を前提とする
 *   - build() 後に実際の値が得られる
 *
 * 使用例:
 *   // 5×5 グリッド
 *   kwm_t::utility::Imos2D<int> imos(5, 5);
 *
 *   // [1,4) × [2,5) に +3
 *   imos.add(1, 2, 4, 5, 3);
 *
 *   // [0,2) × [0,2) に +1
 *   imos.add(0, 0, 2, 2, 1);
 *
 *   imos.build();
 *
 *   int v = imos.get(1, 2);
 *
 * verified:
 *   - https://atcoder.jp/contests/awc0070/submissions/75804201
 */
template <class T>
struct Imos2D {
private:
	std::vector<std::vector<T>> d;
	bool built = false;

public:
	Imos2D() = default;

	Imos2D(int h, int w) {
		init(h, w);
	}

	void init(int h, int w) {
		assert(h >= 0 && w >= 0);

		d.assign(h + 1, std::vector<T>(w + 1, T{}));
		built = false;
	}

	int height() const {
		return (int)d.size() - 1;
	}

	int width() const {
		return d.empty() ? 0 : (int)d[0].size() - 1;
	}

	/**
	 * @brief 長方形領域 [x0,x1) × [y0,y1) に val を加算
	 */
	void add(int x0, int y0, int x1, int y1, T val) {
		assert(!built);

		assert(0 <= x0 && x0 <= x1 && x1 <= height());
		assert(0 <= y0 && y0 <= y1 && y1 <= width());

		d[x0][y0] += val;
		d[x1][y0] -= val;
		d[x0][y1] -= val;
		d[x1][y1] += val;
	}

	/**
	 * @brief 累積和を取って復元
	 */
	void build() {
		assert(!built);

		int h = height();
		int w = width();

		for (int i = 0; i <= h; i++)
			for (int j = 0; j < w; j++)
				d[i][j + 1] += d[i][j];

		for (int i = 0; i < h; i++)
			for (int j = 0; j <= w; j++)
				d[i + 1][j] += d[i][j];

		built = true;
	}

	/**
	 * @brief build 後の値を取得
	 */
	T get(int x, int y) const {
		assert(built);

		assert(0 <= x && x < height());
		assert(0 <= y && y < width());

		return d[x][y];
	}

	/**
	 * @brief build 後のグリッドを取得
	 */
	const std::vector<std::vector<T>>& data() const {
		assert(built);
		return d;
	}
};

} // namespace kwm_t::utility

#endif // KWM_T_UTILITY_IMOS_2D_HPP
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int h, w, n; cin >> h >> w >> n;
	kwm_t::utility::Imos2D<int> imos(h, w);
	rep(i, n) {
		int r1, c1, r2, c2;
		cin >> r1 >> c1 >> r2 >> c2;
		imos.add(r1 - 1, c1 - 1, r2, c2, 1);
	}
	imos.build();
	int ans = 0;
	rep(i, h)rep(j, w)if (imos.get(i, j) == 0)ans++;
	cout << ans << endl;
	return 0;
}