This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <cassert>
#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 660
#define MAXS 20
#define INF 20000000000020
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
ll H, W;
int N;
pll arr[MAX];
ll ans = INF;
int st[MAX * 2], en[MAX * 2];
ll U[MAX], D[MAX], UD[MAX];
ll A[MAX][MAX], B[MAX][MAX], C[MAX][MAX];
typedef pair<ll, int> pli;
deque<pli> up, down, su;
ll ys[MAX * 2];
bool test(ll d) {
if (d <= 0) return false;
int i, j;
int p1, p2;
p1 = p2 = 1;
int X = 0;
while (p1 <= N || p2 <= N) {
ll x;
if (p1 > N) x = arr[p2].second + d;
else if (p2 > N) x = arr[p1].second;
else x = min(arr[p1].second, arr[p2].second + d);
ys[X++] = x;
while (p1 <= N && arr[p1].second == x) p1++;
while (p2 <= N && arr[p2].second + d == x) p2++;
}
for (i = 0; i < X; i++) U[i] = D[i] = UD[i] = 0, st[i] = en[i] = 0;
for (i = 1; i <= N; i++) {
int l, r;
l = lower_bound(ys, ys + X, arr[i].second) - ys;
r = lower_bound(ys, ys + X, arr[i].second + d) - ys;
st[l]++;
en[r]++;
}
int il, ir;
il = ir = 0;
for (i = 0; i < X; i++) {
ir += st[i];
il += en[i];
if (il == ir) {
UD[i] = INF;
continue;
}
U[i] = A[il + 1][ir];
D[i] = B[il + 1][ir];
UD[i] = C[il + 1][ir];
}
up.clear();
down.clear();
su.clear();
ll mn = INF;
j = 0;
for (i = 0; i < X - 1; i++) {
while (up.size() && up.back().first <= U[i]) up.pop_back();
up.emplace_back(U[i], i);
while (down.size() && down.back().first <= D[i]) down.pop_back();
down.emplace_back(D[i], i);
while (su.size() && su.back().first <= UD[i]) su.pop_back();
su.emplace_back(UD[i], i);
while (j + 1 <= i && ys[i + 1] - ys[j + 1] >= W) j++;
while (up.size() && up.front().second < j) up.pop_front();
while (down.size() && down.front().second < j) down.pop_front();
while (su.size() && su.front().second < j) su.pop_front();
if (ys[i + 1] - ys[j] >= W) mn = min(mn, max(0ll + up.front().first + down.front().first, (ll)su.front().first));
}
if (mn >= INF) return false;
ans = min(ans, mn + d - 1);
return true;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> H >> W >> N;
int i, j, k;
vector<ll> ls;
ls.push_back(W);
for (i = 1; i <= N; i++) cin >> arr[i].first >> arr[i].second;
for (i = 1; i <= N; i++) {
for (j = i + 1; j <= N; j++) ls.push_back(W - abs(arr[j].second - arr[i].second));
for (j = i + 1; j <= N; j++) ls.push_back(abs(arr[j].second - arr[i].second));
for (j = i + 1; j <= N; j++) ls.push_back(abs(arr[j].second - arr[i].second) + W);
ls.push_back(arr[i].second);
ls.push_back(arr[i].second + 1);
ls.push_back(W - arr[i].second);
ls.push_back(W - arr[i].second + 1);
}
sort(arr + 1, arr + N + 1, [&](pii p1, pii p2) {return p1.second < p2.second; });
for (i = 1; i <= N; i++) {
vector<ll> v;
A[i][i] = arr[i].first - 1;
B[i][i] = H - arr[i].first;
v.push_back(arr[i].first);
for (j = i + 1; j <= N; j++) {
v.insert(lower_bound(v.begin(), v.end(), arr[j].first), arr[j].first);
for (k = 0; k + 1 < v.size(); k++) C[i][j] = max(C[i][j], v[k + 1] - v[k] - 1);
A[i][j] = v[0] - 1;
B[i][j] = H - v.back();
}
}
sort(ls.begin(), ls.end());
ls.erase(unique(ls.begin(), ls.end()), ls.end());
reverse(ls.begin(), ls.end());
for (auto v : ls) if (!test(v)) break;
cout << ans << ln;
}
Compilation message (stderr)
cultivation.cpp: In function 'int main()':
cultivation.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for (k = 0; k + 1 < v.size(); k++) C[i][j] = max(C[i][j], v[k + 1] - v[k] - 1);
| ~~~~~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |