제출 #961110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
961110		danikoynov	Cultivation (JOI17_cultivation)	C++14	15 / 100	2064 ms	126512 KiB

cultivation

#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


*/

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20