#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 310
#define MAXS 20
#define INF 1e9
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define fmax(a, b) a = max(a, b)
#ifdef _MSC_VER
# include <intrin.h>
# define __builtin_popcount __popcnt
#endif
int X[MAX];
int Y[MAX];
int N, R, C;
int l[MAX];
int r[MAX];
vector<int> locs[MAX];
int M;
int limu[MAX];
int limd[MAX];
int lims[MAX];
vector<int> xs;
vector<int> st[MAX];
vector<int> en[MAX];
int mn;
int chk(int hor) {
int i;
vector<int> ys = { mn };
for (i = 1; i <= N; i++) ys.push_back(Y[i]), ys.push_back(Y[i] + C + 1), ys.push_back(Y[i] + hor + 1);
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
for (i = 1; i <= N; i++) {
l[i] = lower_bound(ys.begin(), ys.end(), Y[i]) - ys.begin();
r[i] = lower_bound(ys.begin(), ys.end(), Y[i] + hor + 1) - ys.begin() - 1;
}
int K = ys.size();
int ml = lower_bound(ys.begin(), ys.end(), mn) - ys.begin();
for (i = 0; i <= K; i++) st[i].clear(), en[i].clear();
for (i = 1; i <= N; i++) st[l[i]].push_back(i), en[r[i]].push_back(i);
multiset<int> s;
multiset<int> delta;
for (i = 0; i < K; i++) {
for (auto v : st[i]) {
int x = X[v];
if (s.size()) {
auto rit = s.upper_bound(x);
if (rit == s.end()) delta.insert(x - *s.rbegin());
else if (rit == s.begin()) delta.insert(*s.begin() - x);
else {
auto lit = prev(rit);
delta.erase(delta.find(*rit - *lit));
delta.insert(*rit - x);
delta.insert(x - *lit);
}
}
s.insert(x);
}
if (s.empty()) lims[i] = R + C + 100;
else {
lims[i] = 0;
limu[i] = *s.begin() - 1;
limd[i] = R - *s.rbegin();
}
if (delta.size()) lims[i] = *delta.rbegin() - 1;
for (auto v : en[i]) {
int x = X[v];
s.erase(s.find(x));
if (s.size()) {
auto rit = s.upper_bound(x);
if (rit == s.end()) delta.erase(delta.find(x - *s.rbegin()));
else if (rit == s.begin()) delta.erase(delta.find((*s.begin() - x)));
else {
auto lit = prev(rit);
delta.insert(*rit - *lit);
delta.erase(delta.find((*rit - x)));
delta.erase(delta.find((x - *lit)));
}
}
}
}
int j = -1;
int sum = 0;
priority_queue<pii> up, down, su;
int ans = 2e9;
for (i = 0; i < K - 1; i++) {
up.emplace(limu[i], i);
down.emplace(limd[i], i);
su.emplace(lims[i], i);
while (j + 1 < i && ys[i] - ys[j + 1] >= C) j++;
while (up.size() && up.top().second <= j && j + 1 < ml) up.pop();
while (down.size() && down.top().second <= j) down.pop();
while (su.size() && su.top().second <= j) su.pop();
if (ys[i + 1] - 1 - ((!~j) ? 0 : ys[j]) >= C) ans = min(ans, max(up.top().first + down.top().first, su.top().first));
}
if (ans > R) return 2e9;
return ans + hor;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> R >> C >> N;
vector<int> v;
int i, j;
mn = C;
for (i = 1; i <= N; i++) cin >> X[i] >> Y[i], mn = min(mn, Y[i]), xs.push_back(X[i]);
mn--;
for (i = 1; i <= N; i++) Y[i] -= mn;
for (i = 0; i <= C; i++) v.push_back(i);
/*for (i = 1; i <= N; i++) for (j = 1; j <= N; j++) v.push_back(max(0, abs(Y[i] - Y[j]) - 1)), v.push_back(Y[i] - 1 + C - Y[j]);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
while (v.back() >= C) v.pop_back();
*/
int ans = R + C;
for (auto h : v) ans = min(ans, chk(h));
cout << ans << ln;
}
Compilation message
cultivation.cpp: In function 'int chk(int)':
cultivation.cpp:91:6: warning: unused variable 'sum' [-Wunused-variable]
91 | int sum = 0;
| ^~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:111:9: warning: unused variable 'j' [-Wunused-variable]
111 | int i, j;
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
251 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
251 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
