Submission #961012

#TimeUsernameProblemLanguageResultExecution timeMemory
961012danikoynovCultivation (JOI17_cultivation)C++14
15 / 100
2056 ms262144 KiB
#include <bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; const int maxn = 310, maxc = 42; int n, r, c; int x[maxn], y[maxn]; struct node { node *lc, *rc; int mx, cnt, lazy; node() { mx = 0; cnt = 0; lazy = 0; lc = rc = NULL; } }; void make_kids(node *root, int left, int right) { int 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, int left, int right, int qleft, int qright, int 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; } int 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 { int y, x_up, x_dw; int t; line(int _y = 0, int _x_dw = 0, int _x_up = 0, int _t = 0) { y = _y; x_up = _x_up; x_dw = _x_dw; t = _t; } }; struct event { int t; line l; event(int _t = 0, line _l = line()) { t = _t; l = _l; } }; set < int > 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(int h, int w) { for (int rel : set_x) { node *root = new node(); root -> cnt = r; unordered_map < ll, ll > prec; vector < event > events; for (int 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 (int 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 { int lx = max(rel, cur.l.x_dw); int rx = min(rel + r - 1, cur.l.x_up); update_range(root, rel, rel + r - 1, lx, rx, cur.l.t); } } /*for (int y : set_y) { cout << y << " : " << prec[y] << endl; }*/ for (int 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 (int i = 1; i <= n; i ++) cin >> x[i] >> y[i]; for (int i = 1; i <= n; i ++) { set_x.insert(x[i]); set_y.insert(y[i]); } //cout << check(3, 2) << endl; //exit(0); int ans = r + c - 2; int to_c = c * 2 + 1; while(to_c > 1) { int lf = 1, rf = r * 2; while(lf <= rf) { int mf = (lf + rf) / 2; if (check(mf, to_c - 1)) rf = mf - 1; else lf = mf + 1; } if (lf > r * 2) break; int to_r = lf; lf = 1; rf = c * 2; while(lf <= rf) { int 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 (int h = 1; h <= r * 2; h ++) { int lf = 1, rf = c * 2; while(lf <= rf) { int 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 */
#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...