Submission #961014

#TimeUsernameProblemLanguageResultExecution timeMemory
961014danikoynovCultivation (JOI17_cultivation)C++14
15 / 100
2067 ms262144 KiB
#include <bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; const ll maxn = 310; ll n, r, c; ll x[maxn], y[maxn]; struct node { node *lc, *rc; ll mx, cnt, lazy; node() { mx = 0; cnt = 0; lazy = 0; lc = rc = NULL; } }; void make_kids(node *root, ll left, ll right) { ll mid = (left + right) / 2; if (root -> lc == NULL) { root -> lc = new node(); root -> lc -> cnt = mid - left + 1; } if (root -> rc == NULL) { root -> rc = new node(); root -> rc -> cnt = right - mid; } } void push_lazy(node *root) { root -> mx += root -> lazy; if (root -> lc != NULL) { root -> lc -> lazy += root -> lazy; root -> rc -> lazy += root -> lazy; } root -> lazy = 0; } void unite(node *root) { root -> mx = min(root -> lc -> mx, root -> rc -> mx); root -> cnt = 0; if (root -> lc -> mx == root -> mx) root -> cnt += root -> lc -> cnt; if (root -> rc -> mx == root -> mx) root -> cnt += root -> rc -> cnt; } void update_range(node *root, ll left, ll right, ll qleft, ll qright, ll val) { if (left != right) make_kids(root, left, right); push_lazy(root); if (left > qright || right < qleft) return; if (left >= qleft && right <= qright) { root -> lazy += val; push_lazy(root); return; } ll mid = (left + right) / 2; update_range(root -> lc, left, mid, qleft, qright, val); update_range(root -> rc, mid + 1, right, qleft, qright, val); unite(root); ///cout << "return " << left << " " << right << " " << root -> mx << " " << root -> cnt << endl; } struct line { ll y, x_up, x_dw; ll t; line(ll _y = 0, ll _x_dw = 0, ll _x_up = 0, ll _t = 0) { y = _y; x_up = _x_up; x_dw = _x_dw; t = _t; } }; struct event { ll t; line l; event(ll _t = 0, line _l = line()) { t = _t; l = _l; } }; set < ll > set_x, set_y; bool cmp(event e1, event e2) { ///if (e1.l.y == e2.l2.y) ///return e1.t < e2.t; return e1.l.y < e2.l.y; } bool check(ll h, ll w) { for (ll rel : set_x) { node *root = new node(); root -> cnt = r; unordered_map < ll, ll > prec; vector < event > events; for (ll i = 1; i <= n; i ++) { event op, en; op.t = en.t = 1; op.l = line(y[i], x[i], x[i] + h - 1, 1); en.l = line(y[i] + w, x[i], x[i] + h - 1, -1); events.push_back(op); events.push_back(en); } for (ll y : set_y) { events.push_back(event(2, line(y, 0, 0, 0))); events.push_back(event(2, line(y + c, 0, 0, 0))); } sort(events.begin(), events.end(), cmp); ll area = 0; ll last = 0; //cout << "range " << rel << " " << rel + r - 1 << endl; for (event cur : events) { //cout << "event " << cur.l.y << " area " << area << endl; //if (cur.t == 1) // cout << "line " << cur.l.x_dw << " " << cur.l.x_up << " " << cur.l.t << endl; ll act = r; if (root -> mx == 0) act -= root -> cnt; //cout << "rem " << root -> cnt << endl; area += act * (ll)(cur.l.y - last); last = cur.l.y; if (cur.t == 2) { prec[cur.l.y] = area; } else { ll lx = max(rel, cur.l.x_dw); ll rx = min(rel + r - 1, cur.l.x_up); update_range(root, rel, rel + r - 1, lx, rx, cur.l.t); } } /*for (ll y : set_y) { cout << y << " : " << prec[y] << endl; }*/ for (ll y : set_y) { ll ar = prec[y + c] - prec[y]; if (ar == (ll)(r) * (ll)(c)) return true; } } return false; } void solve() { cin >> r >> c; cin >> n; for (ll i = 1; i <= n; i ++) cin >> x[i] >> y[i]; for (ll i = 1; i <= n; i ++) { set_x.insert(x[i]); set_y.insert(y[i]); } //cout << check(3, 2) << endl; //exit(0); ll ans = r + c - 2; ll to_c = c * 2 + 1; while(to_c > 1) { ll lf = 1, rf = r * 2; while(lf <= rf) { ll mf = (lf + rf) / 2; if (check(mf, to_c - 1)) rf = mf - 1; else lf = mf + 1; } if (lf > r * 2) break; ll to_r = lf; lf = 1; rf = c * 2; while(lf <= rf) { ll mf = (lf + rf) / 2; if (check(to_r, mf)) rf = mf - 1; else lf = mf + 1; } to_c = lf; ans = min(ans, to_r + to_c - 2); } /**for (ll h = 1; h <= r * 2; h ++) { ll lf = 1, rf = c * 2; while(lf <= rf) { ll w = (lf + rf) / 2; if (check(h, w)) rf = w - 1; else lf = w + 1; } if (lf <= c * 2) ans = min(ans, lf + h - 2); }*/ cout << ans << endl; } int main() { solve(); return 0; } /** 40 30 50 19 20 18 16 34 28 5 8 28 21 24 13 7 1 28 23 28 18 12 6 3 6 18 8 40 27 22 19 23 22 8 6 9 12 16 10 27 25 26 19 4 9 40 26 21 22 10 8 5 2 30 25 12 12 3 1 24 14 5 3 4 8 19 9 21 16 6 3 38 29 27 20 37 25 36 24 22 20 29 26 30 19 16 14 3 3 39 25 5 7 20 15 13 12 33 30 27 16 25 14 1000000000 1000000000 17 822413671 70423910 260075513 431043546 300945721 793553248 142848049 163787897 392462410 831950868 699005697 111397300 444396260 130450496 642691616 595456084 467968916 463598810 159764248 611476406 929313754 539645102 365153650 964108073 906780716 373514044 970118116 655138295 257280896 236115217 909808245 942097331 523555293 969550238 */
#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...