oj.uz

Submission #961012

# Submission time Handle Problem Language Result Execution time Memory
961012 2024-04-11T11:31:17 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;
    int to_c = c * 2 + 1;
    while(to_c > 1)
    {
         int lf = 1, rf = r * 2;
         while(lf <= rf)
         {
              int mf = (lf + rf) / 2;
              if (check(mf, to_c - 1))
                    rf = mf - 1;
              else
                    lf = mf + 1;
         }
         if (lf > r * 2)
          break;

         int to_r = lf;
         lf = 1;
         rf = c * 2;
         while(lf <= rf)
         {
              int 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 (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 344 KB Output is correct
4 Correct 0 ms 344 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 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 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 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 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 344 KB Output is correct
4 Correct 0 ms 344 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 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 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 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 6 ms 1372 KB Output is correct
18 Correct 23 ms 2136 KB Output is correct
19 Correct 27 ms 5716 KB Output is correct
20 Correct 4 ms 860 KB Output is correct
21 Correct 225 ms 28600 KB Output is correct
22 Correct 142 ms 9316 KB Output is correct
23 Correct 19 ms 2648 KB Output is correct
24 Correct 172 ms 7544 KB Output is correct
25 Correct 149 ms 7760 KB Output is correct
26 Correct 357 ms 10316 KB Output is correct
27 Correct 343 ms 9044 KB Output is correct
28 Correct 206 ms 9040 KB Output is correct
29 Correct 208 ms 5544 KB Output is correct
30 Correct 188 ms 5488 KB Output is correct
31 Correct 174 ms 5456 KB Output is correct
32 Correct 207 ms 6064 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 344 KB Output is correct
4 Correct 0 ms 344 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 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 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 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 6 ms 1372 KB Output is correct
18 Correct 23 ms 2136 KB Output is correct
19 Correct 27 ms 5716 KB Output is correct
20 Correct 4 ms 860 KB Output is correct
21 Correct 225 ms 28600 KB Output is correct
22 Correct 142 ms 9316 KB Output is correct
23 Correct 19 ms 2648 KB Output is correct
24 Correct 172 ms 7544 KB Output is correct
25 Correct 149 ms 7760 KB Output is correct
26 Correct 357 ms 10316 KB Output is correct
27 Correct 343 ms 9044 KB Output is correct
28 Correct 206 ms 9040 KB Output is correct
29 Correct 208 ms 5544 KB Output is correct
30 Correct 188 ms 5488 KB Output is correct
31 Correct 174 ms 5456 KB Output is correct
32 Correct 207 ms 6064 KB Output is correct
33 Correct 27 ms 348 KB Output is correct
34 Execution timed out 2056 ms 38268 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 220 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 220 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 344 KB Output is correct
4 Correct 0 ms 344 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 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 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 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 6 ms 1372 KB Output is correct
18 Correct 23 ms 2136 KB Output is correct
19 Correct 27 ms 5716 KB Output is correct
20 Correct 4 ms 860 KB Output is correct
21 Correct 225 ms 28600 KB Output is correct
22 Correct 142 ms 9316 KB Output is correct
23 Correct 19 ms 2648 KB Output is correct
24 Correct 172 ms 7544 KB Output is correct
25 Correct 149 ms 7760 KB Output is correct
26 Correct 357 ms 10316 KB Output is correct
27 Correct 343 ms 9044 KB Output is correct
28 Correct 206 ms 9040 KB Output is correct
29 Correct 208 ms 5544 KB Output is correct
30 Correct 188 ms 5488 KB Output is correct
31 Correct 174 ms 5456 KB Output is correct
32 Correct 207 ms 6064 KB Output is correct
33 Correct 27 ms 348 KB Output is correct
34 Execution timed out 2056 ms 38268 KB Time limit exceeded
35 Halted 0 ms 0 KB -