Submission #419205

#	Time	Username	Problem	Language	Result	Execution time	Memory
419205		Kevin_Zhang_TW	Cultivation (JOI17_cultivation)	C++17	100 / 100	709 ms	2968 KiB

cultivation

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
 
const int MAX_N = 305;
 
#define int ll
const int inf = 1ll << 55;
int R, C, n;
vector<pair<int,int>> loc;
 
bool can_cover(int ul, int dl, int al, int bl) {
 
	vector<vector<int>> pf_sum(50, vector<int> (50) );
	for (auto [x, y] : loc) {
		int A = y - ul, B = y + dl;
		int C = x - bl, D = x + al;
		chmax(A, 1ll);
		chmax(C, 1ll);
		chmin(D, R);
		chmin(B, ::C);
		++pf_sum[C][A];
		--pf_sum[D+1][A];
		--pf_sum[C][B+1];
		++pf_sum[D+1][B+1];
	}
 
	for (int i = 1;i <= R;++i) {
		for (int j = 1;j <= C;++j) {
			pf_sum[i][j] += pf_sum[i-1][j] + pf_sum[i][j-1] - pf_sum[i-1][j-1];
			if (pf_sum[i][j] == 0) return false;
		}
	}
	return true;
}
 

int pre_ly[MAX_N][MAX_N], pre_ry[MAX_N][MAX_N];

void pre_proc() {
	for (int i = 0;i < n;++i) {
		auto [x, y] = loc[i];

		set<int> ys;
		ys.insert(-inf);
		ys.insert(inf);

		for (int j = i+1;j < n;++j) {
			auto [cx, cy] = loc[j];
			if (cx == x) continue;

			auto it = ys.lower_bound(cy);
			int ly = *prev(it), ry = *it;  ys.insert(cy);

			pre_ly[i][j] = ly, pre_ry[i][j] = ry;

		}
	}
}
int cal_up(int ul) {
	int dnmn = 0;
	{
		vector<int> ys;
		for (auto [x, y] : loc)
			ys.pb(y - ul);
		sort(AI(ys));
		int lst_end = 0;
		for (int y : ys) {
			chmax(dnmn, y - 1 - lst_end);
			lst_end = y + ul;
		}
		chmax(dnmn, C - lst_end);
	}
 
	vector<vector<tuple<int,int,int>>> must;
	vector<tuple<int,int,int>> op2;
	vector<int> sep;
 
	sep.reserve(n * n * 5);
 
 
	DE(ul);

	auto must_op = [&]() {
		must.pb();
		must.back().reserve(n * n * 5);
		//sort(AI(loc));
 
		for (int i = 0;i < n;++i) {
			auto [x, y] = loc[i];
 
			auto allmx = [&](int l, int r, int v) {
				chmax(l, dnmn);
				chmin(r, C);
				if (l > r) return;
				sep.pb(l), sep.pb(r+1);
				must.back().pb(l, r+1, v - x - 1);
			};
 
			int nl = 1, nr = C;
			for (int j = i+1;j < n;++j) {
				auto [cx, cy] = loc[j];
				if (cx == x) continue;
				if (cy <= y) chmax(nl, cy + 1);
				if (cy >= y) chmin(nr, cy - ul - 1);
			}
 
			if (nl > nr) continue;
			if (nl == 1) allmx(0, C, R + 1);
			else if (nl <= nr) allmx(0, nr - nl, R + 1);
		}
	};
	auto all_op = [&]() {
 
		for (int i = 0;i < n;++i) {
			auto [x, y] = loc[i];
 
			auto segmx = [&](int l, int r, int v) {
				chmax(l, dnmn);
				chmin(r, C);
				if (l > r) return;
				sep.pb(l), sep.pb(r+1);
				op2.pb(l, r+1, v - x - 1);
			};
 
			for (int j = i+1;j < n;++j) {
				auto [cx, cy] = loc[j];
				if (cx == x) continue;
 
				//auto it = ys.lower_bound(cy);
				int ly = pre_ly[i][j], ry = pre_ry[i][j];
				//int ly = *prev(it), ry = *it;  ys.insert(cy);
				int s = 0, e = min(C - ly - 1, (ry - ul - 1) - ly - 1);
				if (cy >= y) chmax(s, cy - ul - y);
				else chmax(s, y - ul - cy);
				if (y <= ly || ry <= y || s > e || ry == cy || ry - ul <= 1) continue;

				segmx(s, e, cx);
			}
		}
   	};
 
	all_op();
	must_op();
	for (auto &[x, y] : loc) 
		x = R - x + 1;
	reverse(AI(loc));

	must_op();

	for (auto &[x, y] : loc) 
		x = R - x + 1;
	reverse(AI(loc));
 
	sep.pb(C+1);
 
	sort(AI(sep)); sep.erase(unique(AI(sep)), end(sep));
 
	priority_queue<pair<int,int>> pq, pq2[2];
	pq.emplace(0, inf);
	pq2[0].emplace(0, inf);
	pq2[1].emplace(0, inf);
 
	sort(AI(op2));
 
	sort(AI(must[0]));
	sort(AI(must[1]));
 
	int h{}, h2[2]{};
 
	int res = inf;
	for (int i = 0;i+1 < sep.size();++i) {
		int M = sep[i];
		auto add_in = [&](auto &pq, auto &op, int &i) {
			for (;i < op.size();++i) {
				auto [l, r, v] = op[i];
				if (l > M) break;
				pq.emplace(v, r);
			}
		};
		auto pops = [&](auto &pq) -> ll{
			while (pq.top().second <= sep[i])
				pq.pop();
			return pq.top().first;
		};
 
		add_in(pq, op2, h);
		add_in(pq2[0], must[0], h2[0]);
		add_in(pq2[1], must[1], h2[1]);
 
		chmin(res, sep[i] + ul + 
				max(pops(pq), pops(pq2[0]) + pops(pq2[1])));
 
	}
	return res;
}
int brute() {
	int res = inf;
	for (int ul = 0;ul <= C;++ul) for (int dl = 0;dl <= C;++dl) {
		int A = R, B = R;
		while (A > 0 && can_cover(ul, dl, A-1, B)) --A;
		while (B > 0 && can_cover(ul, dl, A, B-1)) --B;
		if (can_cover(ul, dl, A, B)) {
			if (chmin(res, ul + dl + A + B))
				DE(ul, dl, A, B);
		}
	}
	return res;
}
 
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> R >> C >> n; loc.resize(n);
	for (auto &[x, y] : loc) {
		cin >> x >> y;
	}
	sort(AI(loc));
 
	int res = inf;
 
	vector<int> ys;
	for (auto [x, y] : loc) ys.pb(y);
 
	sort(AI(ys)); ys.erase(unique(AI(ys)), end(ys));
 
	pre_proc();

	for (int y : ys) {
		int cur = cal_up(y - 1);
		chmin(res, cur);
	}
 
	cout << res << '\n';
}

Compilation message (stderr)

cultivation.cpp: In function 'll cal_up(ll)':
cultivation.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
cultivation.cpp:96:2: note: in expansion of macro 'DE'
   96 |  DE(ul);
      |  ^~
cultivation.cpp:186:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |  for (int i = 0;i+1 < sep.size();++i) {
      |                 ~~~~^~~~~~~~~~~~
cultivation.cpp: In instantiation of 'cal_up(ll)::<lambda(auto:23&, auto:24&, ll&)> [with auto:23 = std::priority_queue<std::pair<long long int, long long int> >; auto:24 = std::vector<std::tuple<long long int, long long int, long long int> >; ll = long long int]':
cultivation.cpp:201:20:   required from here
cultivation.cpp:189:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |    for (;i < op.size();++i) {
      |          ~~^~~~~~~~~~~
cultivation.cpp: In function 'll brute()':
cultivation.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
cultivation.cpp:219:5: note: in expansion of macro 'DE'
  219 |     DE(ul, dl, A, B);
      |     ^~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 20 / 20
• Subtask 6: 20 / 20