oj.uz

Submission #961110

# Submission time Handle Problem Language Result Execution time Memory
961110 2024-04-11T13:59:08 Z danikoynov Cultivation (JOI17_cultivation) C++14
15 / 100
 2000 ms 126512 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 125832 KB Output is correct
2 Correct 23 ms 125624 KB Output is correct
3 Correct 21 ms 125532 KB Output is correct
4 Correct 21 ms 125488 KB Output is correct
5 Correct 22 ms 125468 KB Output is correct
6 Correct 21 ms 125520 KB Output is correct
7 Correct 22 ms 125532 KB Output is correct
8 Correct 21 ms 125532 KB Output is correct
9 Correct 21 ms 125532 KB Output is correct
10 Correct 22 ms 125528 KB Output is correct
11 Correct 21 ms 125532 KB Output is correct
12 Correct 21 ms 125532 KB Output is correct
13 Correct 21 ms 125532 KB Output is correct
14 Correct 22 ms 125564 KB Output is correct
15 Correct 20 ms 125524 KB Output is correct
16 Correct 21 ms 125528 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 125832 KB Output is correct
2 Correct 23 ms 125624 KB Output is correct
3 Correct 21 ms 125532 KB Output is correct
4 Correct 21 ms 125488 KB Output is correct
5 Correct 22 ms 125468 KB Output is correct
6 Correct 21 ms 125520 KB Output is correct
7 Correct 22 ms 125532 KB Output is correct
8 Correct 21 ms 125532 KB Output is correct
9 Correct 21 ms 125532 KB Output is correct
10 Correct 22 ms 125528 KB Output is correct
11 Correct 21 ms 125532 KB Output is correct
12 Correct 21 ms 125532 KB Output is correct
13 Correct 21 ms 125532 KB Output is correct
14 Correct 22 ms 125564 KB Output is correct
15 Correct 20 ms 125524 KB Output is correct
16 Correct 21 ms 125528 KB Output is correct
17 Correct 26 ms 125520 KB Output is correct
18 Correct 47 ms 125704 KB Output is correct
19 Correct 47 ms 125528 KB Output is correct
20 Correct 25 ms 125524 KB Output is correct
21 Correct 213 ms 125688 KB Output is correct
22 Correct 165 ms 125532 KB Output is correct
23 Correct 37 ms 125684 KB Output is correct
24 Correct 223 ms 125720 KB Output is correct
25 Correct 175 ms 125716 KB Output is correct
26 Correct 399 ms 125776 KB Output is correct
27 Correct 336 ms 125784 KB Output is correct
28 Correct 254 ms 125720 KB Output is correct
29 Correct 220 ms 125628 KB Output is correct
30 Correct 229 ms 125788 KB Output is correct
31 Correct 222 ms 125788 KB Output is correct
32 Correct 245 ms 125788 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 125832 KB Output is correct
2 Correct 23 ms 125624 KB Output is correct
3 Correct 21 ms 125532 KB Output is correct
4 Correct 21 ms 125488 KB Output is correct
5 Correct 22 ms 125468 KB Output is correct
6 Correct 21 ms 125520 KB Output is correct
7 Correct 22 ms 125532 KB Output is correct
8 Correct 21 ms 125532 KB Output is correct
9 Correct 21 ms 125532 KB Output is correct
10 Correct 22 ms 125528 KB Output is correct
11 Correct 21 ms 125532 KB Output is correct
12 Correct 21 ms 125532 KB Output is correct
13 Correct 21 ms 125532 KB Output is correct
14 Correct 22 ms 125564 KB Output is correct
15 Correct 20 ms 125524 KB Output is correct
16 Correct 21 ms 125528 KB Output is correct
17 Correct 26 ms 125520 KB Output is correct
18 Correct 47 ms 125704 KB Output is correct
19 Correct 47 ms 125528 KB Output is correct
20 Correct 25 ms 125524 KB Output is correct
21 Correct 213 ms 125688 KB Output is correct
22 Correct 165 ms 125532 KB Output is correct
23 Correct 37 ms 125684 KB Output is correct
24 Correct 223 ms 125720 KB Output is correct
25 Correct 175 ms 125716 KB Output is correct
26 Correct 399 ms 125776 KB Output is correct
27 Correct 336 ms 125784 KB Output is correct
28 Correct 254 ms 125720 KB Output is correct
29 Correct 220 ms 125628 KB Output is correct
30 Correct 229 ms 125788 KB Output is correct
31 Correct 222 ms 125788 KB Output is correct
32 Correct 245 ms 125788 KB Output is correct
33 Correct 50 ms 125840 KB Output is correct
34 Execution timed out 2064 ms 126512 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 125680 KB Output is correct
2 Correct 878 ms 125680 KB Output is correct
3 Correct 935 ms 125680 KB Output is correct
4 Execution timed out 2032 ms 125532 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 125680 KB Output is correct
2 Correct 878 ms 125680 KB Output is correct
3 Correct 935 ms 125680 KB Output is correct
4 Execution timed out 2032 ms 125532 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 125832 KB Output is correct
2 Correct 23 ms 125624 KB Output is correct
3 Correct 21 ms 125532 KB Output is correct
4 Correct 21 ms 125488 KB Output is correct
5 Correct 22 ms 125468 KB Output is correct
6 Correct 21 ms 125520 KB Output is correct
7 Correct 22 ms 125532 KB Output is correct
8 Correct 21 ms 125532 KB Output is correct
9 Correct 21 ms 125532 KB Output is correct
10 Correct 22 ms 125528 KB Output is correct
11 Correct 21 ms 125532 KB Output is correct
12 Correct 21 ms 125532 KB Output is correct
13 Correct 21 ms 125532 KB Output is correct
14 Correct 22 ms 125564 KB Output is correct
15 Correct 20 ms 125524 KB Output is correct
16 Correct 21 ms 125528 KB Output is correct
17 Correct 26 ms 125520 KB Output is correct
18 Correct 47 ms 125704 KB Output is correct
19 Correct 47 ms 125528 KB Output is correct
20 Correct 25 ms 125524 KB Output is correct
21 Correct 213 ms 125688 KB Output is correct
22 Correct 165 ms 125532 KB Output is correct
23 Correct 37 ms 125684 KB Output is correct
24 Correct 223 ms 125720 KB Output is correct
25 Correct 175 ms 125716 KB Output is correct
26 Correct 399 ms 125776 KB Output is correct
27 Correct 336 ms 125784 KB Output is correct
28 Correct 254 ms 125720 KB Output is correct
29 Correct 220 ms 125628 KB Output is correct
30 Correct 229 ms 125788 KB Output is correct
31 Correct 222 ms 125788 KB Output is correct
32 Correct 245 ms 125788 KB Output is correct
33 Correct 50 ms 125840 KB Output is correct
34 Execution timed out 2064 ms 126512 KB Time limit exceeded
35 Halted 0 ms 0 KB -