oj.uz

Submission #961013

# Submission time Handle Problem Language Result Execution time Memory
961013 2024-04-11T11:33:44 Z danikoynov Cultivation (JOI17_cultivation) C++14
15 / 100
 2000 ms 262144 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
{
    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 7 ms 1372 KB Output is correct
18 Correct 24 ms 2140 KB Output is correct
19 Correct 28 ms 5716 KB Output is correct
20 Correct 5 ms 860 KB Output is correct
21 Correct 201 ms 28756 KB Output is correct
22 Correct 155 ms 9580 KB Output is correct
23 Correct 17 ms 2464 KB Output is correct
24 Correct 188 ms 7484 KB Output is correct
25 Correct 149 ms 7660 KB Output is correct
26 Correct 361 ms 10268 KB Output is correct
27 Correct 318 ms 9368 KB Output is correct
28 Correct 234 ms 9144 KB Output is correct
29 Correct 199 ms 5380 KB Output is correct
30 Correct 198 ms 5532 KB Output is correct
31 Correct 195 ms 5452 KB Output is correct
32 Correct 213 ms 6136 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 7 ms 1372 KB Output is correct
18 Correct 24 ms 2140 KB Output is correct
19 Correct 28 ms 5716 KB Output is correct
20 Correct 5 ms 860 KB Output is correct
21 Correct 201 ms 28756 KB Output is correct
22 Correct 155 ms 9580 KB Output is correct
23 Correct 17 ms 2464 KB Output is correct
24 Correct 188 ms 7484 KB Output is correct
25 Correct 149 ms 7660 KB Output is correct
26 Correct 361 ms 10268 KB Output is correct
27 Correct 318 ms 9368 KB Output is correct
28 Correct 234 ms 9144 KB Output is correct
29 Correct 199 ms 5380 KB Output is correct
30 Correct 198 ms 5532 KB Output is correct
31 Correct 195 ms 5452 KB Output is correct
32 Correct 213 ms 6136 KB Output is correct
33 Correct 27 ms 612 KB Output is correct
34 Execution timed out 2069 ms 27416 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 310 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 310 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 7 ms 1372 KB Output is correct
18 Correct 24 ms 2140 KB Output is correct
19 Correct 28 ms 5716 KB Output is correct
20 Correct 5 ms 860 KB Output is correct
21 Correct 201 ms 28756 KB Output is correct
22 Correct 155 ms 9580 KB Output is correct
23 Correct 17 ms 2464 KB Output is correct
24 Correct 188 ms 7484 KB Output is correct
25 Correct 149 ms 7660 KB Output is correct
26 Correct 361 ms 10268 KB Output is correct
27 Correct 318 ms 9368 KB Output is correct
28 Correct 234 ms 9144 KB Output is correct
29 Correct 199 ms 5380 KB Output is correct
30 Correct 198 ms 5532 KB Output is correct
31 Correct 195 ms 5452 KB Output is correct
32 Correct 213 ms 6136 KB Output is correct
33 Correct 27 ms 612 KB Output is correct
34 Execution timed out 2069 ms 27416 KB Time limit exceeded
35 Halted 0 ms 0 KB -