제출 #961110

#제출 시각아이디문제언어결과실행 시간메모리
961110danikoynovCultivation (JOI17_cultivation)C++14
15 / 100
2064 ms126512 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 { int lc, rc; ll mx, cnt, lazy; node() { mx = 0; cnt = 0; lazy = 0; lc = rc = -1; } }; const int maxt = 4e6 + 10; node tree[maxt]; int nxt; void make_kids(int root, ll left, ll right) { ll mid = (left + right) / 2; if (tree[root].lc == -1) { tree[root].lc = ++ nxt; tree[tree[root].lc] = node(); tree[tree[root].lc].cnt = mid - left + 1; } if (tree[root].rc == -1) { tree[root].rc = ++ nxt; tree[tree[root].rc] = node(); tree[tree[root].rc].cnt = right - mid; } } void push_lazy(int root) { tree[root].mx += tree[root].lazy; if (tree[root].lc != -1) { tree[tree[root].lc].lazy += tree[root].lazy; tree[tree[root].rc].lazy += tree[root].lazy; } tree[root].lazy = 0; } void unite(int root) { tree[root].mx = min(tree[tree[root].lc].mx, tree[tree[root].rc].mx); tree[root].cnt = 0; if (tree[tree[root].lc].mx == tree[root].mx) tree[root].cnt += tree[tree[root].lc].cnt; if (tree[tree[root].rc].mx == tree[root].mx) tree[root].cnt += tree[tree[root].rc].cnt; } void update_range(int 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) { tree[root].lazy += val; push_lazy(root); return; } ll mid = (left + right) / 2; update_range(tree[root].lc, left, mid, qleft, qright, val); update_range(tree[root].rc, mid + 1, right, qleft, qright, val); unite(root); //cout << "return " << left << " " << right << " " << tree[root].mx << " " << tree[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) { int root = 1; nxt = 1; tree[root] = node(); tree[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 (tree[root].mx == 0) act -= tree[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]); } 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...