Submission #27974

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
27974	2017-07-14T14:23:56 Z	큐브러버(#1177)	Cultivation (JOI17_cultivation)	C++14	5 / 100	0 ms	8332 KB

cultivation

#include <cstdio>
#include <deque>
#include <algorithm>

using namespace std;

pair<int, int> a[303];
pair<pair<int, int>, int> t[300003];
int tx[303], ty[303];
int L[606][606], R[606][606];
int l, mx[606];
deque<int> dq1, dq2, dq3, dq4, dq5, dq6, dq7;

void Del(int i, int j) {
	R[i][L[i][j]] = R[i][j];
	L[i][R[i][j]] = L[i][j];
	if (tx[R[i][j]] - tx[L[i][j]] - 1 > mx[i]) mx[i] = tx[R[i][j]] - tx[L[i][j]] - 1;
}

void Push(deque<int> &dq, int x) {
	while (!dq.empty() && dq.back() < x) dq.pop_back();
	dq.push_back(x);
}

void Pop(deque<int> &dq, int x) {
	if (dq.front() == x) dq.pop_front();
}

int Front(deque<int> &dq) {
	return dq.empty() ? 0 : dq.front();
}

int main() {
	int LL, RR, TT;
	int tn, tt, ttt, tttt, rr;
	int i, j, jj, k, kk, m, n;
	scanf("%d%d%d", &n, &m, &l);
	if (l == 1) {
		printf("%d\n", n + m - 2);
		return 0;
	}
	for (i = 0; i < l; i++) scanf("%d%d", &a[i].first, &a[i].second);
	for (i = 0; i < l; i++) {
		t[i].first = a[i];
		t[i].second = i;
		ty[i] = a[i].second;
	}
	sort(t, t + l);
	sort(ty, ty + l);
	tx[0] = 1;
	tx[l + 1] = n;
	for (i = 0; i < l; i++) {
		a[t[i].second].first = i + 1;
		tx[i + 1] = t[i].first.first;
		a[i].second = lower_bound(ty, ty + l, a[i].second) - ty;
	}
	tt = 0;
	ttt = 0;
	tttt = m - ty[l - 1] + ty[0] - 1;
	for (i = 1; i < l; i++) {
		if (ty[i] - ty[i - 1] - 1 > tt) tt = ty[i] - ty[i - 1] - 1;
		if (ty[i] - ty[i - 1] - 1 > tttt) tttt = ty[i] - ty[i - 1] - 1;
	}
	for (i = 0; i <= l; i++) if (tx[i + 1] - tx[i] - 1 > ttt) ttt = tx[i + 1] - tx[i] - 1;
	tn = 0;
	for (i = 0; i < l; i++) for (j = 0; j < l; j++) if (a[i].second <= a[j].second) {
		t[tn].first.first = ty[a[j].second] - ty[a[i].second];
		t[tn].first.second = -a[j].second - 1;
		t[tn].second = -a[i].first - 1;
		tn++;
		t[tn].first.first = ty[a[j].second] - ty[a[i].second];
		t[tn].first.second = -a[i].second - l - 1;
		t[tn].second = -a[j].first - 1;
		tn++;
		tt = m - ty[a[j].second] + ty[a[i].second] - 1;
		for (k = a[i].second; k < a[j].second; k++) if (tt < ty[k + 1] - ty[k] - 1) tt = ty[k + 1] - ty[k] - 1;
		t[tn].first.first = tt;
		t[tn].first.second = a[i].second;
		t[tn].second = a[j].second;
		tn++;
	}
	sort(t, t + tn);
	for (i = 0; i < l + l; i++) for (j = 0; j <= l; j++) {
		L[i][j + 1] = j;
		R[i][j] = j + 1;
		mx[i] = ttt;
	}
	for (i = 0; i < l; i++) {
		for (j = 0; j < a[i].second; j++) Del(j, a[i].first);
		for (j = a[i].second + l + 1; j < l + l; j++) Del(j, a[i].first);
	}
	rr = 1e9;
	for (i = tn - 1; i >= 0; i = j) {
		if (t[i].first.second >= 0) {
			LL = RR = TT = 0;
			for (k = t[i].first.second; k < l; k++) {
				if (tx[R[k][0]] - tx[0] > LL) LL = tx[R[k][0]] - tx[0];
				if (tx[l + 1] - tx[L[k][l + 1]] > RR) RR = tx[l + 1] - tx[L[k][l + 1]];
				if (mx[k] > TT) TT = mx[k];
			}
			for (k = 0; k <= t[i].second; k++) {
				if (tx[R[k + l][0]] - tx[0] > LL) LL = tx[R[k + l][0]] - tx[0];
				if (tx[l + 1] - tx[L[k + l][l + 1]] > RR) RR = tx[l + 1] - tx[L[k + l][l + 1]];
				if (mx[k + l] > TT) TT = mx[k + l];
			}
			rr = min(rr, max(LL + RR, TT) + t[i].first.first);
			j = i - 1;
		}
		else {
			dq1.clear(); dq2.clear(); dq3.clear(); dq4.clear(); dq5.clear(); dq6.clear(); dq7.clear();
			for (k = 0; k < l; k++) {
				Push(dq1, mx[k]);
				Push(dq2, tx[R[k][0]] - tx[0]);
				Push(dq3, tx[l + 1] - tx[L[k][l + 1]]);
			}
			for (j = 0, jj = kk = l; j < l && ty[l - 1] + t[i].first.first >= ty[j] + m - 1; j++) {
				while (kk < l + l && (j + l == kk || ty[kk - l - 1] + t[i].first.first < ty[j] + m - 1)) {
					Push(dq4, mx[kk]);
					Push(dq5, tx[R[kk][0]] - tx[0]);
					Push(dq6, tx[l + 1] - tx[L[kk][l + 1]]);
					if (j + l != kk) Push(dq7, ty[kk - l] - ty[kk - l - 1] - 1);
					kk++;
				}
				while (jj < kk && ty[jj] + t[i].first.first < ty[j]) {
					Pop(dq4, mx[jj]);
					Pop(dq5, tx[R[jj][0]] - tx[0]);
					Pop(dq6, tx[l + 1] - tx[L[jj][l + 1]]);
					jj++;
				}
				rr = min(rr, max(max(Front(dq1), Front(dq4)), max(Front(dq2), Front(dq5)) + max(Front(dq3), Front(dq6))) + max(t[i].first.first + 1, max(m - ty[kk - l - 1] + ty[j] - 1, Front(dq7))));
				Pop(dq1, mx[j]);
				Pop(dq2, tx[R[j][0]] - tx[0]);
				Pop(dq3, tx[l + 1] - tx[L[j][l + 1]]);
				if (j + l + 1 != kk) Pop(dq7, ty[j + 1] - ty[j] - 1);
			}
			for (j = i; j >= 0 && t[i].first.first == t[j].first.first && t[j].first.second < 0; j--) Del(-t[j].first.second - 1, -t[j].second - 1);
		}
	}
	printf("%d\n", rr);
}

Compilation message

cultivation.cpp: In function 'int main()':
cultivation.cpp:37:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &l);
                             ^
cultivation.cpp:42:66: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 0; i < l; i++) scanf("%d%d", &a[i].first, &a[i].second);
                                                                  ^

Subtask #1
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	8332 KB	Output is correct
2	Correct	8332 KB	Output is correct
3	Correct	8332 KB	Output is correct
4	Correct	8332 KB	Output is correct
5	Correct	8332 KB	Output is correct
6	Correct	8332 KB	Output is correct
7	Correct	8332 KB	Output is correct
8	Correct	8332 KB	Output is correct
9	Correct	8332 KB	Output is correct
10	Correct	8332 KB	Output is correct
11	Correct	8332 KB	Output is correct
12	Correct	8332 KB	Output is correct
13	Correct	8332 KB	Output is correct
14	Correct	8332 KB	Output is correct
15	Correct	8332 KB	Output is correct
16	Correct	8332 KB	Output is correct

Subtask #2
0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	8332 KB	Output is correct
2	Correct	8332 KB	Output is correct
3	Correct	8332 KB	Output is correct
4	Correct	8332 KB	Output is correct
5	Correct	8332 KB	Output is correct
6	Correct	8332 KB	Output is correct
7	Correct	8332 KB	Output is correct
8	Correct	8332 KB	Output is correct
9	Correct	8332 KB	Output is correct
10	Correct	8332 KB	Output is correct
11	Correct	8332 KB	Output is correct
12	Correct	8332 KB	Output is correct
13	Correct	8332 KB	Output is correct
14	Correct	8332 KB	Output is correct
15	Correct	8332 KB	Output is correct
16	Correct	8332 KB	Output is correct
17	Correct	8332 KB	Output is correct
18	Correct	8332 KB	Output is correct
19	Incorrect	8332 KB	Output isn't correct
20	Halted	0 KB	-

Subtask #3
0 / 15.0

#	Verdict	Memory	Grader output
1	Correct	8332 KB	Output is correct
2	Correct	8332 KB	Output is correct
3	Correct	8332 KB	Output is correct
4	Correct	8332 KB	Output is correct
5	Correct	8332 KB	Output is correct
6	Correct	8332 KB	Output is correct
7	Correct	8332 KB	Output is correct
8	Correct	8332 KB	Output is correct
9	Correct	8332 KB	Output is correct
10	Correct	8332 KB	Output is correct
11	Correct	8332 KB	Output is correct
12	Correct	8332 KB	Output is correct
13	Correct	8332 KB	Output is correct
14	Correct	8332 KB	Output is correct
15	Correct	8332 KB	Output is correct
16	Correct	8332 KB	Output is correct
17	Correct	8332 KB	Output is correct
18	Correct	8332 KB	Output is correct
19	Incorrect	8332 KB	Output isn't correct
20	Halted	0 KB	-

Subtask #4
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	8332 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	8332 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	Verdict	Memory	Grader output
1	Correct	8332 KB	Output is correct
2	Correct	8332 KB	Output is correct
3	Correct	8332 KB	Output is correct
4	Correct	8332 KB	Output is correct
5	Correct	8332 KB	Output is correct
6	Correct	8332 KB	Output is correct
7	Correct	8332 KB	Output is correct
8	Correct	8332 KB	Output is correct
9	Correct	8332 KB	Output is correct
10	Correct	8332 KB	Output is correct
11	Correct	8332 KB	Output is correct
12	Correct	8332 KB	Output is correct
13	Correct	8332 KB	Output is correct
14	Correct	8332 KB	Output is correct
15	Correct	8332 KB	Output is correct
16	Correct	8332 KB	Output is correct
17	Correct	8332 KB	Output is correct
18	Correct	8332 KB	Output is correct
19	Incorrect	8332 KB	Output isn't correct
20	Halted	0 KB	-

Submission #27974

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 10.0

Subtask #3 0 / 15.0

Subtask #4 0 / 30.0

Subtask #5 0 / 20.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 10.0

Subtask #3
0 / 15.0

Subtask #4
0 / 30.0

Subtask #5
0 / 20.0

Subtask #6
0 / 20.0