Submission #965327

#	Time	Username	Problem	Language	Result	Execution time	Memory
965327		Gromp15	Garden (JOI23_garden)	C++17	45 / 100	3026 ms	396784 KiB

garden

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
const int INF = 1e9;
void test_case() {
	int n, m, D;
	cin >> n >> m >> D;
	vector<ar<int, 2>> a(n), b(m);
	for (auto &x : a) cin >> x[0] >> x[1];
	for (auto &x : b) cin >> x[0] >> x[1];
	if (m <= 8) {
		vector pref(D, vector(D, -INF)), suff(D, vector(D, -INF)), pref2(D, vector(D, -INF)), suff2(D, vector(D, -INF));
		for (auto [x, y] : a) {
			ckmax(pref[x][y], x), ckmax(suff[x][y], x);
			ckmax(pref2[x][y], y), ckmax(suff2[x][y], y);
		}
		for (int i = 0; i < D; i++) for (int j = 0; j < D; j++) {
			if (i) ckmax(pref[i][j], pref[i-1][j]), ckmax(pref2[i][j], pref2[i-1][j]);
			if (j) ckmax(pref[i][j], pref[i][j-1]), ckmax(pref2[i][j], pref2[i][j-1]);
		}
		for (int i = D-1; i >= 0; i--) for (int j = D-1; j >= 0; j--) {
			if (i+1 < D) ckmax(suff[i][j], suff[i+1][j]), ckmax(suff2[i][j], suff2[i+1][j]);
			if (j+1 < D) ckmax(suff[i][j], suff[i][j+1]), ckmax(suff2[i][j], suff2[i][j+1]);
		}
		int ans = 1e9;
		auto contain = [](int A, int B, int C) {
			return A <= B && B <= C;
		};
		for (int i = 0; i < D; i++) for (int j = 0; j < D; j++) {
			int max_x = max(max({i && j ? pref[i-1][j-1] + D : -INF, i ? pref[i-1][D-1] + D : -INF, j ? pref[D-1][j-1] : -INF}), suff[i][j]);
			int max_y = max(max({i && j ? pref2[i-1][j-1] + D : -INF, i ? pref2[i-1][D-1] : -INF, j ? pref2[D-1][j-1] + D : -INF}), suff2[i][j]);
			assert(max_x >= i);
			assert(max_y >= j);
			vector<ar<int, 2>> each;
			for (auto [x, y] : b) {
				if (x < i) x += D;
				if (y < j) y += D;
				if (contain(i, x, max_x) || contain(j, y, max_y)) continue;
				each.push_back({x, y});
			}
			set<int> other;
			sort(all(each));
			if (each.empty()) ckmin(ans, (max_x - i + 1) * (max_y - j + 1));
			for (int k = sz(each) - 1; k >= 0; k--) {
				assert(each[k][0] > max_x);
				ckmin(ans, (each[k][0] - i + 1) * (max(other.size() ? *prev(other.end()) : -1, max_y) - j + 1));
				other.insert(each[k][1]);
			}
		}
		cout << ans << '\n';
	}
	else {
		vector<vector<ar<int, 3>>> each(D);
		for (int i = 0; i < n; i++) {
			each[a[i][0]].push_back({a[i][1], i, 0});
		}
		for (int i = 0; i < m; i++) {
			each[b[i][0]].push_back({-1, i + n, 1});
		}
		int ans2 = 1e9;
		for (int i = 0; i < D; i++) {
			auto calc = [&](int top) {
				int l = i, r = top;
				// use [l, r] y
				vector<int> got(n + m);
				int need = n + m;
				for (int i = 0; i < m; i++) {
					// b[1] is y
					if ((l <= b[i][1] && b[i][1] <= r) || (l <= b[i][1] + D && b[i][1] + D <= r)) {
						got[i + n]++;
						need--;
					}
				}
				int left = 0, bst = INF;
				for (int j = 0; j < 2 * D; j++) {
					for (auto [y, pos, tp] : each[j % D]) {
						if (tp == 1) {
							if (got[pos]++ == 0) need--;
						}
						else {
							// [l,r ] need to enclose y
							if ((l <= y && y <= r) || (l <= y+D && y+D <= r)) {
								if (got[pos]++ == 0) need--;
							}
						}
					}
					bool ok = need == 0;
					int last_good = left;
					while (need == 0) {
						last_good = left;
						for (auto [y, pos, tp] : each[left % D]) {
							if (tp == 1) {
								if (--got[pos] == 0) need++;
							}
							else {
								// [l,r ] need to enclose y
								if ((l <= y && y <= r) || (l <= y+D && y+D <= r)) {
									if (--got[pos] == 0) need++;
								}
							}
						}
						left++;
					}
					if (ok) ckmin(bst, j - last_good + 1);
				}
				return bst == INF ? -1 : bst;
			};
			for (int j = i; j < i + D; j++) {
				int res = calc(j);
				//cout << "I: " << i << " " << j << " " << res << '\n';
				if (~res) ckmin(ans2, (j - i + 1) * res);
			}
		}
		cout << ans2 << '\n';
	}
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
//    cin >> t;
    while (t--) test_case();
}

• Subtask 1: 15 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25