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>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back
const int INF = 2e9;
pii arr[305];
int umx, dmx;
vector<pii> smx; // [l, INF)
int lmi_a = 0;
vector<pii> lmi_u, lmi_d; // [0, r)
vector<pair<pii, int>> lmi_m; // [l, r)
int rmi_a = 0;
vector<pii> rmi_u, rmi_d; // [0, r)
vector<pair<pii, int>> rmi_m; // [l, r)
int smi_a = 0;
vector<pii> smi_u, smi_d; // [0, r)
vector<pair<pii, int>> smi_m; // [l, r)
vector<int> L, M, R;
vector<int> val;
void modify(vector<int> &seg, int ql, int qr, int l, int r, int rt, int v) {
if (ql <= l && qr >= r)
return seg[rt] = max(seg[rt], v), void();
int mid = (l + r) >> 1;
if (ql <= mid)
modify(seg, ql, qr, l, mid, rt << 1, v);
if (qr > mid)
modify(seg, ql, qr, mid + 1, r, rt << 1 | 1, v);
}
void modify(vector<int> &seg, int ql, int qr, int v) { //[ql, qr)
if (ql < qr)
modify(seg, ql, qr - 1, 0, SZ(val) - 1, 1, v);
}
void dfs(vector<int> &seg, int l, int r, int rt, int v, vector<int> &res) {
v = max(v, seg[rt]);
if (l == r)
return res[l] = v, void();
int mid = (l + r) >> 1;
dfs(seg, l, mid, rt << 1, v, res);
dfs(seg, mid + 1, r, rt << 1 | 1, v, res);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int r, c, n, ans;
cin >> r >> c >> n, ans = r + c - 2;
for (int i = 1; i <= n; ++i)
cin >> arr[i].X >> arr[i].Y;
sort(arr + 1, arr + n + 1, [](pii a, pii b){ return a.Y < b.Y; });
lmi_a = arr[1].Y - 1;
rmi_a = c - arr[n].Y;
for (int i = 1, j = 1; i <= n; i = j) {
while (j <= n && arr[i].Y == arr[j].Y)
++j;
if (j <= n)
smi_a = max(smi_a, arr[j].Y - arr[i].Y - 1);
}
smi_a = max(smi_a, lmi_a + rmi_a);
sort(arr + 1, arr + n + 1);
// U
for (int i = 1; i <= n; ++i) {
int lft = -1, rgt = INF;
for (int j = 1; arr[j].X < arr[i].X; ++j) {
if (arr[j].Y >= arr[i].Y)
rgt = min(rgt, arr[j].Y);
if (arr[j].Y <= arr[i].Y)
lft = max(lft, arr[j].Y);
}
if (lft == -1 && rgt == INF)
umx = max(umx, arr[i].X - 1);
else if (lft == -1)
lmi_u.pb(pii(rgt - 1, arr[i].X - 1));
else if (rgt == INF)
rmi_u.pb(pii(c - lft, arr[i].X - 1));
else if (rgt - lft - 1 > 0)
smi_u.pb(pii(rgt - lft - 1, arr[i].X - 1));
}
// M
for (int i = 1; i <= n; ++i)
for (int j = 1; arr[j].X < arr[i].X; ++j) {
int lft = -1, rgt = INF;
for (int k = j + 1; k < i; ++k) {
if (arr[k].X == arr[j].X || arr[k].X == arr[i].X)
continue;
if (arr[k].Y >= arr[i].Y || arr[k].Y >= arr[j].Y)
rgt = min(rgt, arr[k].Y);
if (arr[k].Y <= arr[i].Y || arr[k].Y <= arr[j].Y)
lft = max(lft, arr[k].Y);
}
if (lft == -1 && rgt == INF)
smx.pb(pii(abs(arr[i].Y - arr[j].Y), arr[i].X - arr[j].X - 1));
else if (lft == -1)
lmi_m.pb(make_pair(pii(abs(arr[i].Y - arr[j].Y), rgt - 1), arr[i].X - arr[j].X - 1));
else if (rgt == INF)
rmi_m.pb(make_pair(pii(abs(arr[i].Y - arr[j].Y), c - lft), arr[i].X - arr[j].X - 1));
else if (rgt - lft - 1 > abs(arr[i].Y - arr[i].Y))
smi_m.pb(make_pair(pii(abs(arr[i].Y - arr[j].Y), rgt - lft - 1), arr[i].X - arr[j].X - 1));
}
// D
for (int i = 1; i <= n; ++i) {
int lft = -1, rgt = INF;
for (int j = n; arr[j].X > arr[i].X; --j) {
if (arr[j].Y >= arr[i].Y)
rgt = min(rgt, arr[j].Y);
if (arr[j].Y <= arr[i].Y)
lft = max(lft, arr[j].Y);
}
if (lft == -1 && rgt == INF)
dmx = max(dmx, r - arr[i].X);
else if (lft == -1)
lmi_d.pb(pii(rgt - 1, r - arr[i].X));
else if (rgt == INF)
rmi_d.pb(pii(c - lft, r - arr[i].X));
else if (rgt - lft - 1 > 0)
smi_d.pb(pii(rgt - lft - 1, r - arr[i].X));
}
L.pb(lmi_a);
for (auto p : lmi_u)
L.pb(p.X);
for (auto p : lmi_m) {
L.pb(p.X.X);
L.pb(p.X.Y);
}
for (auto p : lmi_d)
L.pb(p.X);
sort(ALL(L)), L.resize(unique(ALL(L)) - L.begin());
M.pb(smi_a);
for (auto p : smi_u)
M.pb(p.X);
for (auto p : smi_m) {
M.pb(p.X.X);
M.pb(p.X.Y);
}
for (auto p : smi_d)
M.pb(p.X);
sort(ALL(M)), M.resize(unique(ALL(M)) - M.begin());
R.pb(rmi_a);
for (auto p : rmi_u)
R.pb(p.X);
for (auto p : rmi_m) {
R.pb(p.X.X);
R.pb(p.X.Y);
}
for (auto p : rmi_d)
R.pb(p.X);
sort(ALL(R)), R.resize(unique(ALL(R)) - R.begin());
for (int lft : L) {
if (lft < lmi_a)
continue;
val.clear();
if (smi_a >= lft)
val.pb(smi_a);
val.pb(lft + rmi_a);
for (int sum : M)
if (sum >= lft)
val.pb(sum);
for (int rgt : R)
val.pb(rgt + lft);
sort(ALL(val)), val.resize(unique(ALL(val)) - val.begin());
vector<int> seg_u(4 * SZ(val)), res_u(SZ(val));
vector<int> seg_m(4 * SZ(val)), res_m(SZ(val));
vector<int> seg_d(4 * SZ(val)), res_d(SZ(val));
modify(seg_u, 0, SZ(val), umx);
for (auto p : smx)
modify(seg_m, lower_bound(ALL(val), p.X) - val.begin(), SZ(val), p.Y);
modify(seg_d, 0, SZ(val), dmx);
for (auto p : lmi_u)
if (lft < p.X)
modify(seg_u, 0, SZ(val), p.Y);
for (auto p : lmi_m)
if (lft < p.X.Y)
modify(seg_m, lower_bound(ALL(val), p.X.X) - val.begin(), SZ(val), p.Y);
for (auto p : lmi_d)
if (lft < p.X)
modify(seg_d, 0, SZ(val), p.Y);
for (auto p : smi_u)
modify(seg_u, 0, lower_bound(ALL(val), p.X) - val.begin(), p.Y);
for (auto p : smi_m)
modify(seg_m, lower_bound(ALL(val), p.X.X) - val.begin(), lower_bound(ALL(val), p.X.Y) - val.begin(), p.Y);
for (auto p : smi_d)
modify(seg_d, 0, lower_bound(ALL(val), p.X) - val.begin(), p.Y);
for (auto p : rmi_u)
modify(seg_u, 0, lower_bound(ALL(val), p.X + lft) - val.begin(), p.Y);
for (auto p : rmi_m)
modify(seg_m, lower_bound(ALL(val), p.X.X) - val.begin(), lower_bound(ALL(val), p.X.Y + lft) - val.begin(), p.Y);
for (auto p : rmi_d)
modify(seg_d, 0, lower_bound(ALL(val), p.X + lft) - val.begin(), p.Y);
dfs(seg_u, 0, SZ(val) - 1, 1, 0, res_u);
dfs(seg_m, 0, SZ(val) - 1, 1, 0, res_m);
dfs(seg_d, 0, SZ(val) - 1, 1, 0, res_d);
for (int i = 0; i < SZ(val); ++i) {
if (val[i] < smi_a || val[i] - lft < rmi_a)
continue;
ans = min((ll)ans, (ll)val[i] + max((ll)res_m[i], (ll)res_u[i] + (ll)res_d[i]));
}
}
cout << ans << "\n";
}
# | 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... |