Submission #446709

#TimeUsernameProblemLanguageResultExecution timeMemory
446709baluteshihCultivation (JOI17_cultivation)C++14
100 / 100
244 ms976 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...