Submission #205872

#	Time	Username	Problem	Language	Result	Execution time	Memory
205872		ics0503	Cultivation (JOI17_cultivation)	C++17	5 / 100	2080 ms	376 KiB

cultivation

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int n, R, C;
struct xy { int x, y; }a[313];
struct line { int x, ys, ye, pls; };
bool sort_x(line a, line b) { if (a.x != b.x)return a.x < b.x; return a.pls < b.pls; }
int y[121212], val[121212];
struct ND {
	int l, r, min, buf;
}node[1212]; int nn;
void spread(int now) {
	int l = node[now].l, r = node[now].r;
	node[l].buf += node[now].buf; node[l].min += node[now].buf;
	node[r].buf += node[now].buf; node[r].min += node[now].buf;
	node[now].buf = 0;
}
void update(int now) { node[now].min = min(node[node[now].l].min, node[node[now].r].min); }
void insert_g(int now, int s, int e, int l, int r, int pls) {
	if (s != e) {
		if (!node[now].l)node[now].l = ++nn;
		if (!node[now].r)node[now].r = ++nn;
		spread(now);
	}
	if (s == l && e == r) {
		node[now].buf += pls;
		node[now].min += pls;
		return;
	}
	int m = (s + e) / 2;
	if (l <= m) insert_g(node[now].l, s, m, l, min(m, r), pls);
	if (m + 1 <= r)insert_g(node[now].r, m + 1, e, max(m + 1, l), r, pls);
	update(now);
}
int ccnt = 0;
bool simulate(int l, int r, int u, int d) {
	ccnt++;
	for (int i = 1; i <= nn; i++)node[i] = { 0,0,0,0 };
	int i, j, k, yn = 0; nn = 1;
	vector<line>L;
	for (i = 0; i < n; i++) {
		L.push_back({ a[i].x - l, a[i].y - u, a[i].y + d, 1 });
		L.push_back({ a[i].x + r + 1, a[i].y - u,a[i].y + d,-1 });
		y[yn++] = a[i].y - u; y[yn++] = a[i].y + d;
		y[yn++] = a[i].y - u - 1; y[yn++] = a[i].y + d + 1;
	}
	L.push_back({ 1, 1, 1, 0 });
	y[yn++] = 1; y[yn++] = R;
	sort(y, y + yn);
	yn = unique(y, y + yn) - y;
	for (i = 0; i < L.size(); i++) {
		if (L[i].ys < 1)L[i].ys = 1;
		if (R < L[i].ye)L[i].ye = R;
		L[i].ys = lower_bound(y, y + yn, L[i].ys) - y;
		L[i].ye = lower_bound(y, y + yn, L[i].ye) - y;
	}
	sort(L.begin(), L.end(), sort_x);
	int s = lower_bound(y, y + yn, 1) - y;
	int e = lower_bound(y, y + yn, R) - y;
	for (i = s; i <= e; i++)val[i] = 0;
	for (i = 0; i < L.size();) {
		if (L[i].x > C)return true;
		for (j = i; j < L.size() && L[i].x == L[j].x; j++) {
			insert_g(1, s, e, L[j].ys, L[j].ye, L[j].pls);
		}
		if (L[i].x >= 1) {
			if (node[1].min == 0)return false;
		}
		i = j;
	}
	return true;
}
int determine_d(int l, int r, int u) {
	int s = 0, e = R, ret = -1;
	while (s <= e) {
		int m = (s + e) / 2;
		if (simulate(l, r, u, m)) {
			ret = m;
			e = m - 1;
		}
		else {
			s = m + 1;
		}
	}
	return ret;
}

int determine_ud(int l, int r) {
	int s = 0, e = R, ret = -1;
	while (e - s >= 3) {
		int p1 = (s * 2 + e) / 3, p2 = (s + e * 2) / 3;
		int k1 = determine_d(l, r, p1);
		int k2 = determine_d(l, r, p2);
		if (k2 < 0) { s = p2 + 1; continue; }
		if (k1 < 0) { s = p1 + 1; continue; }
		if (p1 + k1 < p2 + k2) e = p2 - 1;
		else if (p1 + k1 > p2 + k2) s = p1 + 1;
		else {
			int ts = p2, te = e, tf;
			while (ts <= te) {
				long long tm = (ts + te) / 2;
				long long g = determine_d(l, r, tm);
				if (g == k2) ts = tm + 1, tf = tm;
				else te = tm - 1;
			}
			if (tf == e) { e = p2 - 1; }
			else {
				int v2 = determine_d(l, r, tf + 1);
				if (k2 > v2)s = tf + 1;
				else e = p2 - 1;
			}
		}
	}

	for (int u = s; u <= e; u++) {
		int d = determine_d(l, r, u);
		if (d == -1)continue;
		if (ret == -1 || ret > u + d) {
			ret = u + d;
		}
	}
	return ret;
}

int determine_rud(int l) {
	int s = 0, e = C, ret = -1;
	while (e - s >= 3) {
		int p1 = (s * 2 + e) / 3, p2 = (s + e * 2) / 3;
		int k1 = determine_ud(l, p1);
		int k2 = determine_ud(l, p2);
		if (k2 < 0) { s = p2 + 1; continue; }
		if (k1 < 0) { s = p1 + 1; continue; }
		if (p1 + k1 < p2 + k2) e = p2;
		else if(p1 + k1 > p2 + k2) s = p1;
		else {
			int ts = p2, te = e, tf;
			while (ts <= te) {
				long long tm = (ts + te) / 2;
				long long g = determine_ud(l, tm);
				if (g == k2) ts = tm + 1, tf = tm;
				else te = tm - 1;
			}
			if (tf == e) { e = p2 - 1; }
			else {
				int v2 = determine_ud(l, tf + 1);
				if (k2 > v2)s = tf + 1;
				else e = p2 - 1;
			}
		}
	}

	for (int r = s; r <= e; r++) {
		int ud = determine_ud(l, r);
		if (ud == -1)continue;
		if (ret == -1 || ret > r + ud) {
			ret = r + ud;
		}
	}
	return ret;
}

int main() {
	int i, j, k; scanf("%d%d%d", &C, &R, &n);
	for (i = 0; i < n; i++)scanf("%d%d", &a[i].x, &a[i].y);
	int l, r, u, d;
	int ans = 1e9;
	for (l = 0; l < C; l++) {
		int rud = determine_rud(l);

		if (rud >= 0) {
			ans = min(ans, l + rud);
		}
	}
	printf("%d", ans);
	return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'bool simulate(int, int, int, int)':
cultivation.cpp:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < L.size(); i++) {
              ~~^~~~~~~~~~
cultivation.cpp:62:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < L.size();) {
              ~~^~~~~~~~~~
cultivation.cpp:64:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j = i; j < L.size() && L[i].x == L[j].x; j++) {
               ~~^~~~~~~~~~
cultivation.cpp:40:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k, yn = 0; nn = 1;
            ^
cultivation.cpp: In function 'int main()':
cultivation.cpp:164:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k; scanf("%d%d%d", &C, &R, &n);
         ^
cultivation.cpp:164:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k; scanf("%d%d%d", &C, &R, &n);
            ^
cultivation.cpp:166:9: warning: unused variable 'r' [-Wunused-variable]
  int l, r, u, d;
         ^
cultivation.cpp:166:12: warning: unused variable 'u' [-Wunused-variable]
  int l, r, u, d;
            ^
cultivation.cpp:166:15: warning: unused variable 'd' [-Wunused-variable]
  int l, r, u, d;
               ^
cultivation.cpp:164:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int i, j, k; scanf("%d%d%d", &C, &R, &n);
               ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:165:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 0; i < n; i++)scanf("%d%d", &a[i].x, &a[i].y);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp: In function 'int determine_ud(int, int)':
cultivation.cpp:109:25: warning: 'tf' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int v2 = determine_d(l, r, tf + 1);
              ~~~~~~~~~~~^~~~~~~~~~~~~~
cultivation.cpp: In function 'int determine_rud(int)':
cultivation.cpp:146:26: warning: 'tf' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int v2 = determine_ud(l, tf + 1);
              ~~~~~~~~~~~~^~~~~~~~~~~

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