oj.uz

Submission #961014

# Submission time Handle Problem Language Result Execution time Memory
961014 2024-04-11T11:34:53 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 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 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 0 ms 348 KB Output is correct
16 Correct 0 ms 344 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 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 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 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 6 ms 1372 KB Output is correct
18 Correct 24 ms 2256 KB Output is correct
19 Correct 32 ms 5556 KB Output is correct
20 Correct 5 ms 860 KB Output is correct
21 Correct 208 ms 28584 KB Output is correct
22 Correct 153 ms 9528 KB Output is correct
23 Correct 17 ms 2280 KB Output is correct
24 Correct 190 ms 7504 KB Output is correct
25 Correct 149 ms 7868 KB Output is correct
26 Correct 358 ms 10208 KB Output is correct
27 Correct 326 ms 9044 KB Output is correct
28 Correct 224 ms 9104 KB Output is correct
29 Correct 202 ms 5492 KB Output is correct
30 Correct 198 ms 5584 KB Output is correct
31 Correct 211 ms 5456 KB Output is correct
32 Correct 214 ms 5968 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 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 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 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 6 ms 1372 KB Output is correct
18 Correct 24 ms 2256 KB Output is correct
19 Correct 32 ms 5556 KB Output is correct
20 Correct 5 ms 860 KB Output is correct
21 Correct 208 ms 28584 KB Output is correct
22 Correct 153 ms 9528 KB Output is correct
23 Correct 17 ms 2280 KB Output is correct
24 Correct 190 ms 7504 KB Output is correct
25 Correct 149 ms 7868 KB Output is correct
26 Correct 358 ms 10208 KB Output is correct
27 Correct 326 ms 9044 KB Output is correct
28 Correct 224 ms 9104 KB Output is correct
29 Correct 202 ms 5492 KB Output is correct
30 Correct 198 ms 5584 KB Output is correct
31 Correct 211 ms 5456 KB Output is correct
32 Correct 214 ms 5968 KB Output is correct
33 Correct 29 ms 612 KB Output is correct
34 Execution timed out 2067 ms 26528 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 272 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 272 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 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 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 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 6 ms 1372 KB Output is correct
18 Correct 24 ms 2256 KB Output is correct
19 Correct 32 ms 5556 KB Output is correct
20 Correct 5 ms 860 KB Output is correct
21 Correct 208 ms 28584 KB Output is correct
22 Correct 153 ms 9528 KB Output is correct
23 Correct 17 ms 2280 KB Output is correct
24 Correct 190 ms 7504 KB Output is correct
25 Correct 149 ms 7868 KB Output is correct
26 Correct 358 ms 10208 KB Output is correct
27 Correct 326 ms 9044 KB Output is correct
28 Correct 224 ms 9104 KB Output is correct
29 Correct 202 ms 5492 KB Output is correct
30 Correct 198 ms 5584 KB Output is correct
31 Correct 211 ms 5456 KB Output is correct
32 Correct 214 ms 5968 KB Output is correct
33 Correct 29 ms 612 KB Output is correct
34 Execution timed out 2067 ms 26528 KB Time limit exceeded
35 Halted 0 ms 0 KB -