| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 27973 |
2017-07-14T14:23:38 Z |
큐브러버(#1177) |
Cultivation (JOI17_cultivation) |
C++14 |
|
0 ms |
8332 KB |
#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, 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);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
8332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
8332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
8332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
8332 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
8332 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
8332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
8332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
8332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
8332 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
8332 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
8332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
8332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
8332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
8332 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
8332 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
8332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
8332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
8332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
8332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
8332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
8332 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
8332 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
