Submission #961014

#	Time	Username	Problem	Language	Result	Execution time	Memory
961014		danikoynov	Cultivation (JOI17_cultivation)	C++14	15 / 100	2067 ms	262144 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
{
    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


*/

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