Submission #8963204

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

template <typename M>
class segment_tree {
	using T = typename M::type;
	const int n;
	vector<T> data;
	int expand(int x) {
		int res;
		for (res = 1; res < x; res <<= 1);
		return res;
	}
public:
	segment_tree(int n_) : n(expand(n_)), data(n * 2, M::id()) {}
	segment_tree(int n_, T val) : n(expand(n_)), data(n * 2, val) {}
	void init(const vector<T>& data_) {
		for (int i = 0; i < (int)data_.size(); i++)
			data[i + n] = data_[i];
		for (int i = n - 1; i >= 0; i--)
			data[i] = M::op(data[i * 2], data[i * 2 + 1]);
	}
	void update(int p, T val) {
		data[p += n] = val;
		while (p >>= 1) data[p] = M::op(data[p * 2], data[p * 2 + 1]);
	}
	T find(int l, int r) {
		l += n; r += n + 1;
		T res1 = M::id(), res2 = M::id();
		while (l < r) {
			if (l & 1) res1 = M::op(res1, data[l++]);
			if (r & 1) res2 = M::op(data[--r], res2);
			l >>= 1; r >>= 1;
		}
		return M::op(res1, res2);
	}
};

int main()
{
	int H, W, K;
	cin >> H >> W >> K;
	vector<vector<int>> a(H, vector<int>(W, 1));
	for (int i = 0; i < K; i++) {
		int x, y;
		cin >> x >> y; --x, --y;
		a[x][y] = 0;
	}
	if (K == H * W) {
		cout << 0 << endl;
		return 0;
	}
	vector<vector<int>> dp1(H, vector<int>(W, 0)), dp2(H, vector<int>(W, 0));
	auto dp3 = dp1;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) if (a[i][j]) {
			dp1[i][j] = i == 0 ? 1 : dp1[i - 1][j] + 1;
		}
	}
	for (int i = H - 1; i >= 0; i--) {
		for (int j = 0; j < W; j++) if (a[i][j]) {
			dp2[i][j] = i + 1 == H ? 1 : dp2[i + 1][j] + 1;
		}
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) if (a[i][j]) {
			dp3[i][j] = i == 0 || j == 0 ? 1 : dp3[i - 1][j - 1] + 1;
		}
	}
	int res = 1;
	for (int i = 0; i < W; i++) {
		vector<vector<int>> ad(H + 1);
		for (int j = 0; i + j < W && j < H; j++) {
			int x = j, y = i + j;
			if (!a[x][y]) continue;
			int v = min(dp1[x][y], dp3[x][y]);
			assert(0 <= j + 1 - v);
			ad[j + 1 - v].push_back(j + 1);
		}
		set<int> st;
		for (int j = 0; i + j < W && j < H; j++) {
			if (st.count(j)) st.erase(j);
			for (auto v : ad[j]) {
				st.insert(v);
			}
			int x = j, y = i + j;
			if (!a[x][y]) {
				st.clear();
				continue;
			}
			int v = dp2[x][y];
			auto it = st.upper_bound(j + v);
			if (it == st.begin()) continue;
			res = max(res, *prev(it) - j);
		}
	}
	for (int i = 1; i < H; i++) {
		vector<vector<int>> ad(W + 1);
		for (int j = 0; i + j < H && j < W; j++) {
			int x = i + j, y = j;
			if (!a[x][y]) continue;
			int v = min(dp1[x][y], dp3[x][y]);
			assert(0 <= j + 1 - v);
			ad[j + 1 - v].push_back(j + 1);
		}
		set<int> st;
		for (int j = 0; i + j < H && j < W; j++) {
			if (st.count(j)) st.erase(j);
			for (auto v : ad[j]) {
				st.insert(v);
			}
			int x = i + j, y = j;
			if (!a[x][y]) {
				st.clear();
				continue;
			}
			int v = dp2[x][y];
			auto it = st.upper_bound(j + v);
			if (it == st.begin()) continue;
			res = max(res, *prev(it) - j);
		}
	}
	cout << res << endl;
	return 0;
}

Submission Info

Judge Result