#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;
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>>> op2, must;
vector<int> sep;
DE(ul);
auto all_op = [&]() {
op2.pb();
must.pb();
sort(AI(loc));
for (int i = 0;i < n;++i) {
auto [x, y] = loc[i];
//DE(x, y);
auto segmx = [&](int l, int r, int v) {
chmax(l, dnmn);
chmin(r, C);
if (l > r) return;
//DE(l, r, v - x - 1);
sep.pb(l), sep.pb(r+1);
op2.back().pb(l, r+1, v - x - 1);
};
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);
};
set<int> ys;
ys.insert(-inf);
ys.insert(inf);
int nl = 0, nr = C + 1;
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);
DE(cx, cy);
auto it = ys.lower_bound(cy);
int ly = *prev(it), ry = *it; ys.insert(cy);
int s = -1, e = min(C - ly, ry - ul - 1 - ly);
if (y <= ly || y >= ry) continue;
if (cy >= y) s = max<ll>(0, cy - ul - y);
else s = max<ll>(0, y - ul - cy);
segmx(s, e, cx);
}
if (nl == 0) allmx(0, C, R + 1);
else if (nl <= nr) allmx(0, nr - nl + 1, R + 1);
}
DE(op2.size());
for (auto [l, r, v] : op2.back()) {
DE(l, r, v);
}
};
all_op();
for (auto &[x, y] : loc)
x = R - x + 1;
all_op();
for (auto &[x, y] : loc)
x = R - x + 1;
sep.pb(C+1);
sort(AI(sep)); sep.erase(unique(AI(sep)), end(sep));
priority_queue<pair<int,int>> pq[2], pq2[2];
sort(AI(op2[0]));
sort(AI(op2[1]));
sort(AI(must[0]));
sort(AI(must[1]));
int h[2]{}, h2[2]{};
int res = inf;
for (int i = 0;i+1 < sep.size();++i) {
auto add_in = [&](auto &pq, auto &op, int &i) {
for (;i < op.size();++i) {
auto [l, r, v] = op[i];
if (l > sep[i]) break;
pq.emplace(v, r);
}
};
auto pops = [&](auto &pq) -> ll{
while (pq.size() && pq.top().second <= sep[i])
pq.pop();
return pq.size() ? pq.top().first : 0;
};
add_in(pq[0], op2[0], h[0]);
add_in(pq[1], op2[1], h[1]);
add_in(pq2[0], must[0], h2[0]);
add_in(pq2[1], must[1], h2[1]);
chmin(res, sep[i] + ul +
max({pops(pq[0]), pops(pq[1]), pops(pq2[0]) + pops(pq2[1])}));
}
DE(ul, res);
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);
// location should be the same
for (int y : ys) {
chmin(res, cal_up(y - 1));
}
cout << res << '\n';
}
Compilation message
cultivation.cpp: In function 'll cal_up(ll)':
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
cultivation.cpp:43:2: note: in expansion of macro 'DE'
43 | DE(ul);
| ^~
cultivation.cpp: In lambda function:
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
cultivation.cpp:82:5: note: in expansion of macro 'DE'
82 | DE(cx, cy);
| ^~
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
cultivation.cpp:97:3: note: in expansion of macro 'DE'
97 | DE(op2.size());
| ^~
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
cultivation.cpp:99:4: note: in expansion of macro 'DE'
99 | DE(l, r, v);
| ^~
cultivation.cpp:98:13: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
98 | for (auto [l, r, v] : op2.back()) {
| ^~~~~~~~~
cultivation.cpp: In function 'll cal_up(ll)':
cultivation.cpp:124: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]
124 | 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:138:29: required from here
cultivation.cpp:126: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]
126 | for (;i < op.size();++i) {
| ~~^~~~~~~~~~~
cultivation.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
cultivation.cpp:147:2: note: in expansion of macro 'DE'
147 | DE(ul, res);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
