oj.uz

Submission #961007

# Submission time Handle Problem Language Result Execution time Memory
961007 2024-04-11T11:26:02 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 used[4 * maxc][4 * maxc];
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 ++)
        for (int w = 1; w <= c * 2; w ++)
        {
            /**for (int i = 0; i < 4 * maxc; i ++)
                for (int j = 0; j < 4 * maxc; j ++)
                    used[i][j] = 0;

            for (int i = 1; i <= n; i ++)
            {

                for (int dx = x[i]; dx < x[i] + h; dx ++)
                    for (int dy = y[i]; dy < y[i] + w; dy ++)
                    {
                        ///assert(dx < 2 * maxc && dy < 2 * maxc);
                        used[dx][dy] = 1;
                    }
            }

            bool done = false;
            for (int sx : set_x)
               for (int sy : set_y)
                {

                    bool tf = true;

                    for (int i = sx; i < sx + r && tf; i ++)
                        for (int j = sy; j < sy + c; j ++)
                        {
                            ///assert(i < 2 * maxc && j <2 * maxc);
                            if (used[i][j] == 0)
                            {
                                //if (h == 25 && w == 29)
                                //cout << sx << " : " << sy << " " << i << " " << j << endl;
                                tf = false;
                                break;
                            }
                        }

                    if (tf)
                    {
                        done = true;
                        break;
                    }
                }*/

            if (check(h, w))
            {

                ans = min(ans, h + w - 2);
                break;
            }
        }
    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

*/

Compilation message

cultivation.cpp: In function 'void solve()':
cultivation.cpp:196:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  196 |     for (int i = 1; i <= n; i ++)
      |     ^~~
cultivation.cpp:199:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  199 |         for (int i = 1; i <= n; i ++)
      |         ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 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 1 ms 440 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 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 1 ms 440 KB Output is correct
17 Correct 18 ms 3160 KB Output is correct
18 Correct 101 ms 8940 KB Output is correct
19 Correct 317 ms 56476 KB Output is correct
20 Correct 24 ms 2724 KB Output is correct
21 Correct 1160 ms 163824 KB Output is correct
22 Correct 797 ms 52132 KB Output is correct
23 Correct 546 ms 61408 KB Output is correct
24 Correct 879 ms 33952 KB Output is correct
25 Correct 885 ms 45260 KB Output is correct
26 Correct 1512 ms 44188 KB Output is correct
27 Correct 918 ms 27216 KB Output is correct
28 Correct 865 ms 39312 KB Output is correct
29 Correct 546 ms 15696 KB Output is correct
30 Correct 837 ms 23032 KB Output is correct
31 Correct 760 ms 22528 KB Output is correct
32 Correct 761 ms 22196 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 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 1 ms 440 KB Output is correct
17 Correct 18 ms 3160 KB Output is correct
18 Correct 101 ms 8940 KB Output is correct
19 Correct 317 ms 56476 KB Output is correct
20 Correct 24 ms 2724 KB Output is correct
21 Correct 1160 ms 163824 KB Output is correct
22 Correct 797 ms 52132 KB Output is correct
23 Correct 546 ms 61408 KB Output is correct
24 Correct 879 ms 33952 KB Output is correct
25 Correct 885 ms 45260 KB Output is correct
26 Correct 1512 ms 44188 KB Output is correct
27 Correct 918 ms 27216 KB Output is correct
28 Correct 865 ms 39312 KB Output is correct
29 Correct 546 ms 15696 KB Output is correct
30 Correct 837 ms 23032 KB Output is correct
31 Correct 760 ms 22528 KB Output is correct
32 Correct 761 ms 22196 KB Output is correct
33 Execution timed out 2008 ms 2220 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 195 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 195 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 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 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 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 1 ms 440 KB Output is correct
17 Correct 18 ms 3160 KB Output is correct
18 Correct 101 ms 8940 KB Output is correct
19 Correct 317 ms 56476 KB Output is correct
20 Correct 24 ms 2724 KB Output is correct
21 Correct 1160 ms 163824 KB Output is correct
22 Correct 797 ms 52132 KB Output is correct
23 Correct 546 ms 61408 KB Output is correct
24 Correct 879 ms 33952 KB Output is correct
25 Correct 885 ms 45260 KB Output is correct
26 Correct 1512 ms 44188 KB Output is correct
27 Correct 918 ms 27216 KB Output is correct
28 Correct 865 ms 39312 KB Output is correct
29 Correct 546 ms 15696 KB Output is correct
30 Correct 837 ms 23032 KB Output is correct
31 Correct 760 ms 22528 KB Output is correct
32 Correct 761 ms 22196 KB Output is correct
33 Execution timed out 2008 ms 2220 KB Time limit exceeded
34 Halted 0 ms 0 KB -