이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 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... |