oj.uz

Submission #961010

# Submission time Handle Problem Language Result Execution time Memory
961010 2024-04-11T11:28:29 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 int maxn = 310, maxc = 42;

int n, r, c;
int x[maxn], y[maxn];

struct node
{
    node *lc, *rc;
    int mx, cnt, lazy;

    node()
    {
        mx = 0;
        cnt = 0;
        lazy = 0;
        lc = rc = NULL;
    }
};


void make_kids(node *root, int left, int right)
{
    int 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, int left, int right, int qleft, int qright, int 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;
    }

    int 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
{
    int y, x_up, x_dw;
    int t;

    line(int _y = 0, int _x_dw = 0, int _x_up = 0, int _t = 0)
    {
        y = _y;
        x_up = _x_up;
        x_dw = _x_dw;
        t = _t;
    }
};

struct event
{
    int t;
    line l;

    event(int _t = 0, line _l = line())
    {
        t = _t;
        l = _l;
    }
};

set < int > 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(int h, int w)
{
    for (int rel : set_x)
    {
        node *root = new node();
        root -> cnt = r;
        unordered_map < ll, ll > prec;
        vector < event > events;
        for (int 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 (int 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
            {

                int lx = max(rel, cur.l.x_dw);
                int rx = min(rel + r - 1, cur.l.x_up);
                update_range(root, rel, rel + r - 1, lx, rx, cur.l.t);

            }
        }

        /*for (int y : set_y)
        {
             cout << y << " : " << prec[y] << endl;
        }*/

        for (int 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 (int i = 1; i <= n; i ++)
        cin >> x[i] >> y[i];

    for (int i = 1; i <= n; i ++)
    {
        set_x.insert(x[i]);
        set_y.insert(y[i]);
    }

    //cout << check(3, 2) << endl;
    //exit(0);
    int ans = r + c - 2;
    for (int h = 1; h <= r * 2; h ++)
    {
        int lf = 1, rf = c * 2;
        while(lf <= rf)
        {
            int 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

*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 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 344 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 0 ms 348 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 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 344 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 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 8 ms 1884 KB Output is correct
18 Correct 55 ms 5260 KB Output is correct
19 Correct 62 ms 12372 KB Output is correct
20 Correct 6 ms 860 KB Output is correct
21 Correct 183 ms 27728 KB Output is correct
22 Correct 356 ms 24404 KB Output is correct
23 Correct 69 ms 8564 KB Output is correct
24 Correct 420 ms 18816 KB Output is correct
25 Correct 410 ms 23136 KB Output is correct
26 Correct 645 ms 21392 KB Output is correct
27 Correct 545 ms 17632 KB Output is correct
28 Correct 363 ms 16724 KB Output is correct
29 Correct 373 ms 11472 KB Output is correct
30 Correct 522 ms 16340 KB Output is correct
31 Correct 514 ms 15980 KB Output is correct
32 Correct 448 ms 14272 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 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 344 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 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 8 ms 1884 KB Output is correct
18 Correct 55 ms 5260 KB Output is correct
19 Correct 62 ms 12372 KB Output is correct
20 Correct 6 ms 860 KB Output is correct
21 Correct 183 ms 27728 KB Output is correct
22 Correct 356 ms 24404 KB Output is correct
23 Correct 69 ms 8564 KB Output is correct
24 Correct 420 ms 18816 KB Output is correct
25 Correct 410 ms 23136 KB Output is correct
26 Correct 645 ms 21392 KB Output is correct
27 Correct 545 ms 17632 KB Output is correct
28 Correct 363 ms 16724 KB Output is correct
29 Correct 373 ms 11472 KB Output is correct
30 Correct 522 ms 16340 KB Output is correct
31 Correct 514 ms 15980 KB Output is correct
32 Correct 448 ms 14272 KB Output is correct
33 Correct 30 ms 560 KB Output is correct
34 Execution timed out 2099 ms 28360 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 170 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 170 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 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 344 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 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 8 ms 1884 KB Output is correct
18 Correct 55 ms 5260 KB Output is correct
19 Correct 62 ms 12372 KB Output is correct
20 Correct 6 ms 860 KB Output is correct
21 Correct 183 ms 27728 KB Output is correct
22 Correct 356 ms 24404 KB Output is correct
23 Correct 69 ms 8564 KB Output is correct
24 Correct 420 ms 18816 KB Output is correct
25 Correct 410 ms 23136 KB Output is correct
26 Correct 645 ms 21392 KB Output is correct
27 Correct 545 ms 17632 KB Output is correct
28 Correct 363 ms 16724 KB Output is correct
29 Correct 373 ms 11472 KB Output is correct
30 Correct 522 ms 16340 KB Output is correct
31 Correct 514 ms 15980 KB Output is correct
32 Correct 448 ms 14272 KB Output is correct
33 Correct 30 ms 560 KB Output is correct
34 Execution timed out 2099 ms 28360 KB Time limit exceeded
35 Halted 0 ms 0 KB -