oj.uz

Submission #1009516

# Submission time Handle Problem Language Result Execution time Memory
1009516 2024-06-27T15:19:26 Z boris_mihov Rectangles (IOI19_rect) C++17
59 / 100
 785 ms 1048576 KB 
#include "rect.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>

typedef long long llong;
const int MAXLOG = 12;
const int MAXN = 2500 + 10;
const int INF  = 1e8;

int n, m;
int getLOG[MAXN];
struct SparseMIN
{
    short sparse[MAXN][MAXLOG];
    int len;

    void build(short a[], int length)
    {
        len = length;
        for (int i = 1 ; i <= len ; ++i)
        {
            sparse[i][0] = a[i]; 
        }

        for (int lg = 1 ; (1 << lg) <= len ; ++lg)
        {
            for (int i = 1 ; i + (1 << lg) - 1 <= len ; ++i)
            {
                sparse[i][lg] = std::min(sparse[i][lg - 1], sparse[i + (1 << lg - 1)][lg - 1]);
            }
        }
    }

    int findMIN(int l, int r)
    {
        int lg = getLOG[r - l + 1];
        return std::min(sparse[l][lg], sparse[r - (1 << lg) + 1][lg]);
    }
};

struct SparseMAX
{
    short sparse[MAXN][MAXLOG];
    int len;

    void build(short a[], int length)
    {
        len = length;
        for (int i = 1 ; i <= len ; ++i)
        {
            sparse[i][0] = a[i]; 
        }

        for (int lg = 1 ; (1 << lg) <= len ; ++lg)
        {
            for (int i = 1 ; i + (1 << lg) - 1 <= len ; ++i)
            {
                sparse[i][lg] = std::max(sparse[i][lg - 1], sparse[i + (1 << lg - 1)][lg - 1]);
            }
        }
    }

    int findMAX(int l, int r)
    {
        int lg = getLOG[r - l + 1];
        return std::max(sparse[l][lg], sparse[r - (1 << lg) + 1][lg]);
    }
};

short a[MAXN][MAXN]; // >
short b[MAXN][MAXN]; // v
short c[MAXN][MAXN]; // <
short d[MAXN][MAXN]; // ^
int t[MAXN][MAXN];
short cpy[MAXN];

SparseMIN sparseRD[MAXN];
SparseMAX sparseRU[MAXN];
SparseMIN sparseCL[MAXN];
SparseMAX sparseCR[MAXN];
std::vector <short> possibleColE[MAXN][MAXN];
std::vector <short> possibleRowE[MAXN][MAXN];

bool isOK(int rowB, int colB, int rowE, int colE)
{
    rowB--; colB--; rowE++; colE++;
    if (sparseRD[rowB].findMIN(colB + 1, colE - 1) < rowE) return false;
    if (sparseRU[rowE].findMAX(colB + 1, colE - 1) > rowB) return false;
    if (sparseCL[colB].findMIN(rowB + 1, rowE - 1) < colE) return false;
    if (sparseCR[colE].findMAX(rowB + 1, rowE - 1) > colB) return false;
    return true;
}

llong count_rectangles(std::vector <std::vector<int>> _a)
{
    n = _a.size(); m = _a[0].size();
    for (int i = 0 ; i < n ; ++i)
    {
        for (int j = 0 ; j < m ; ++j)
        {
            t[i + 1][j + 1] = _a[i][j];
        }
    }

    for (int i = 0 ; i <= n + 1 ; ++i)
    {
        t[i][0] = t[i][m + 1] = INF;
    }

    for (int i = 0 ; i <= m + 1 ; ++i)
    {
        t[0][i] = t[n + 1][i] = INF;
    }

    std::stack <int> st;
    for (int i = 1 ; i <= n ; ++i)
    {
        while (st.size()) st.pop(); st.push(m + 1);
        for (int j = m ; j >= 1 ; --j)
        {
            while (t[i][j] > t[i][st.top()])
            {
                st.pop();
            }

            a[i][j] = st.top();
            st.push(j);
        }

        while (st.size()) st.pop(); st.push(0);
        for (int j = 1 ; j <= m ; ++j)
        {
            while (t[i][j] > t[i][st.top()])
            {
                st.pop();
            }

            c[i][j] = st.top();
            st.push(j);
        }
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        while (st.size()) st.pop(); st.push(n + 1);
        for (int j = n ; j >= 1 ; --j)
        {
            while (t[j][i] > t[st.top()][i])
            {
                st.pop();
            }

            b[j][i] = st.top();
            st.push(j);
        }

        while (st.size()) st.pop(); st.push(0);
        for (int j = 1 ; j <= n ; ++j)
        {
            while (t[j][i] > t[st.top()][i])
            {
                st.pop();
            }

            d[j][i] = st.top();
            st.push(j);
        }
    }

    for (int i = 1 ; i <= std::max(n, m) ; ++i)
    {
        getLOG[i] = getLOG[i - 1];
        if ((1 << getLOG[i] + 1) < i) getLOG[i]++;
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        sparseRD[i].build(b[i], m);
        sparseRU[i].build(d[i], m);
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        for (int j = 1 ; j <= n ; ++j)
        {
            cpy[j] = a[j][i];
        }

        sparseCL[i].build(cpy, n);

        for (int j = 1 ; j <= n ; ++j)
        {
            cpy[j] = c[j][i];
        }

        sparseCR[i].build(cpy, n);
    }

    for (int i = 2 ; i <= n ; ++i)
    {
        for (int j = 2 ; j <= m ; ++j)
        {
            if (d[i][j] < i - 1) possibleRowE[d[i][j] + 1][j].push_back(i - 1);
            if (c[i][j] < j - 1) possibleColE[i][c[i][j] + 1].push_back(j - 1);
        }
    }

    for (int i = 2 ; i <= n ; ++i)
    {
        for (int j = 2 ; j <= m ; ++j)
        {
            if (i < b[i - 1][j] && b[i - 1][j] != n + 1 && (possibleRowE[i][j].empty() || possibleRowE[i][j].back() != b[i - 1][j] - 1)) possibleRowE[i][j].push_back(b[i - 1][j] - 1);
            if (j < a[i][j - 1] && a[i][j - 1] != m + 1 && (possibleColE[i][j].empty() || possibleColE[i][j].back() != a[i][j - 1] - 1)) possibleColE[i][j].push_back(a[i][j - 1] - 1);
        }
    }

    int answer = 0;
    for (int rowB = 2 ; rowB < n ; ++rowB)
    {
        for (int colB = 2 ; colB < m ; ++colB)
        {
            for (const int &rowE : possibleRowE[rowB][colB])
            {
                for (const int &colE : possibleColE[rowB][colB])
                {
                    answer += isOK(rowB, colB, rowE, colE);
                }
            }
        }
    }

    return answer;
}

Compilation message

rect.cpp: In member function 'void SparseMIN::build(short int*, int)':
rect.cpp:33:81: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   33 |                 sparse[i][lg] = std::min(sparse[i][lg - 1], sparse[i + (1 << lg - 1)][lg - 1]);
      |                                                                              ~~~^~~
rect.cpp: In member function 'void SparseMAX::build(short int*, int)':
rect.cpp:62:81: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   62 |                 sparse[i][lg] = std::max(sparse[i][lg - 1], sparse[i + (1 << lg - 1)][lg - 1]);
      |                                                                              ~~~^~~
rect.cpp: In function 'llong count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:122:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  122 |         while (st.size()) st.pop(); st.push(m + 1);
      |         ^~~~~
rect.cpp:122:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  122 |         while (st.size()) st.pop(); st.push(m + 1);
      |                                     ^~
rect.cpp:134:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  134 |         while (st.size()) st.pop(); st.push(0);
      |         ^~~~~
rect.cpp:134:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  134 |         while (st.size()) st.pop(); st.push(0);
      |                                     ^~
rect.cpp:149:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  149 |         while (st.size()) st.pop(); st.push(n + 1);
      |         ^~~~~
rect.cpp:149:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  149 |         while (st.size()) st.pop(); st.push(n + 1);
      |                                     ^~
rect.cpp:161:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  161 |         while (st.size()) st.pop(); st.push(0);
      |         ^~~~~
rect.cpp:161:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  161 |         while (st.size()) st.pop(); st.push(0);
      |                                     ^~
rect.cpp:177:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  177 |         if ((1 << getLOG[i] + 1) < i) getLOG[i]++;
      |                   ~~~~~~~~~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 296356 KB Output is correct
2 Correct 144 ms 297552 KB Output is correct
3 Correct 113 ms 297556 KB Output is correct
4 Correct 112 ms 297556 KB Output is correct
5 Correct 108 ms 297560 KB Output is correct
6 Correct 108 ms 297556 KB Output is correct
7 Correct 115 ms 297208 KB Output is correct
8 Correct 109 ms 296784 KB Output is correct
9 Correct 106 ms 297556 KB Output is correct
10 Correct 113 ms 297560 KB Output is correct
11 Correct 108 ms 297552 KB Output is correct
12 Correct 112 ms 297556 KB Output is correct
13 Correct 102 ms 296324 KB Output is correct
14 Correct 104 ms 296532 KB Output is correct
15 Correct 104 ms 296528 KB Output is correct
16 Correct 95 ms 296416 KB Output is correct
17 Correct 94 ms 296272 KB Output is correct
18 Correct 96 ms 296216 KB Output is correct
19 Correct 97 ms 297552 KB Output is correct
20 Correct 100 ms 297352 KB Output is correct
21 Correct 100 ms 296496 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 296356 KB Output is correct
2 Correct 144 ms 297552 KB Output is correct
3 Correct 113 ms 297556 KB Output is correct
4 Correct 112 ms 297556 KB Output is correct
5 Correct 108 ms 297560 KB Output is correct
6 Correct 108 ms 297556 KB Output is correct
7 Correct 115 ms 297208 KB Output is correct
8 Correct 109 ms 296784 KB Output is correct
9 Correct 106 ms 297556 KB Output is correct
10 Correct 113 ms 297560 KB Output is correct
11 Correct 108 ms 297552 KB Output is correct
12 Correct 112 ms 297556 KB Output is correct
13 Correct 102 ms 296324 KB Output is correct
14 Correct 104 ms 296532 KB Output is correct
15 Correct 104 ms 296528 KB Output is correct
16 Correct 95 ms 296416 KB Output is correct
17 Correct 94 ms 296272 KB Output is correct
18 Correct 96 ms 296216 KB Output is correct
19 Correct 97 ms 297552 KB Output is correct
20 Correct 100 ms 297352 KB Output is correct
21 Correct 100 ms 296496 KB Output is correct
22 Correct 97 ms 300388 KB Output is correct
23 Correct 104 ms 300372 KB Output is correct
24 Correct 107 ms 300368 KB Output is correct
25 Correct 107 ms 300116 KB Output is correct
26 Correct 103 ms 299940 KB Output is correct
27 Correct 99 ms 300116 KB Output is correct
28 Correct 105 ms 300192 KB Output is correct
29 Correct 103 ms 299228 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 296356 KB Output is correct
2 Correct 144 ms 297552 KB Output is correct
3 Correct 113 ms 297556 KB Output is correct
4 Correct 112 ms 297556 KB Output is correct
5 Correct 108 ms 297560 KB Output is correct
6 Correct 108 ms 297556 KB Output is correct
7 Correct 115 ms 297208 KB Output is correct
8 Correct 109 ms 296784 KB Output is correct
9 Correct 106 ms 297556 KB Output is correct
10 Correct 113 ms 297560 KB Output is correct
11 Correct 108 ms 297552 KB Output is correct
12 Correct 112 ms 297556 KB Output is correct
13 Correct 102 ms 296324 KB Output is correct
14 Correct 104 ms 296532 KB Output is correct
15 Correct 104 ms 296528 KB Output is correct
16 Correct 95 ms 296416 KB Output is correct
17 Correct 97 ms 300388 KB Output is correct
18 Correct 104 ms 300372 KB Output is correct
19 Correct 107 ms 300368 KB Output is correct
20 Correct 107 ms 300116 KB Output is correct
21 Correct 103 ms 299940 KB Output is correct
22 Correct 99 ms 300116 KB Output is correct
23 Correct 105 ms 300192 KB Output is correct
24 Correct 103 ms 299228 KB Output is correct
25 Correct 94 ms 296272 KB Output is correct
26 Correct 96 ms 296216 KB Output is correct
27 Correct 97 ms 297552 KB Output is correct
28 Correct 100 ms 297352 KB Output is correct
29 Correct 100 ms 296496 KB Output is correct
30 Correct 127 ms 310608 KB Output is correct
31 Correct 106 ms 310500 KB Output is correct
32 Correct 106 ms 310616 KB Output is correct
33 Correct 101 ms 308812 KB Output is correct
34 Correct 110 ms 309332 KB Output is correct
35 Correct 117 ms 309332 KB Output is correct
36 Correct 116 ms 309208 KB Output is correct
37 Correct 110 ms 309076 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 296356 KB Output is correct
2 Correct 144 ms 297552 KB Output is correct
3 Correct 113 ms 297556 KB Output is correct
4 Correct 112 ms 297556 KB Output is correct
5 Correct 108 ms 297560 KB Output is correct
6 Correct 108 ms 297556 KB Output is correct
7 Correct 115 ms 297208 KB Output is correct
8 Correct 109 ms 296784 KB Output is correct
9 Correct 106 ms 297556 KB Output is correct
10 Correct 113 ms 297560 KB Output is correct
11 Correct 108 ms 297552 KB Output is correct
12 Correct 112 ms 297556 KB Output is correct
13 Correct 102 ms 296324 KB Output is correct
14 Correct 104 ms 296532 KB Output is correct
15 Correct 104 ms 296528 KB Output is correct
16 Correct 95 ms 296416 KB Output is correct
17 Correct 97 ms 300388 KB Output is correct
18 Correct 104 ms 300372 KB Output is correct
19 Correct 107 ms 300368 KB Output is correct
20 Correct 107 ms 300116 KB Output is correct
21 Correct 103 ms 299940 KB Output is correct
22 Correct 99 ms 300116 KB Output is correct
23 Correct 105 ms 300192 KB Output is correct
24 Correct 103 ms 299228 KB Output is correct
25 Correct 127 ms 310608 KB Output is correct
26 Correct 106 ms 310500 KB Output is correct
27 Correct 106 ms 310616 KB Output is correct
28 Correct 101 ms 308812 KB Output is correct
29 Correct 110 ms 309332 KB Output is correct
30 Correct 117 ms 309332 KB Output is correct
31 Correct 116 ms 309208 KB Output is correct
32 Correct 110 ms 309076 KB Output is correct
33 Correct 94 ms 296272 KB Output is correct
34 Correct 96 ms 296216 KB Output is correct
35 Correct 97 ms 297552 KB Output is correct
36 Correct 100 ms 297352 KB Output is correct
37 Correct 100 ms 296496 KB Output is correct
38 Correct 174 ms 392788 KB Output is correct
39 Correct 160 ms 385196 KB Output is correct
40 Correct 176 ms 385104 KB Output is correct
41 Correct 657 ms 377556 KB Output is correct
42 Correct 193 ms 406760 KB Output is correct
43 Correct 181 ms 406528 KB Output is correct
44 Correct 192 ms 406612 KB Output is correct
45 Correct 187 ms 399704 KB Output is correct
46 Correct 186 ms 383784 KB Output is correct
47 Correct 195 ms 386384 KB Output is correct
48 Correct 249 ms 391252 KB Output is correct
49 Correct 230 ms 391508 KB Output is correct
50 Correct 168 ms 354388 KB Output is correct
51 Correct 176 ms 346764 KB Output is correct
52 Correct 231 ms 390228 KB Output is correct
53 Correct 230 ms 390228 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 317916 KB Output is correct
2 Correct 101 ms 314804 KB Output is correct
3 Correct 107 ms 317776 KB Output is correct
4 Correct 104 ms 296384 KB Output is correct
5 Correct 110 ms 317776 KB Output is correct
6 Correct 107 ms 317908 KB Output is correct
7 Correct 108 ms 317872 KB Output is correct
8 Correct 107 ms 317776 KB Output is correct
9 Correct 109 ms 317776 KB Output is correct
10 Correct 105 ms 317164 KB Output is correct
11 Correct 98 ms 317520 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 296272 KB Output is correct
2 Correct 96 ms 296216 KB Output is correct
3 Correct 97 ms 297552 KB Output is correct
4 Correct 100 ms 297352 KB Output is correct
5 Correct 100 ms 296496 KB Output is correct
6 Correct 98 ms 296528 KB Output is correct
7 Correct 560 ms 699588 KB Output is correct
8 Runtime error 785 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 296356 KB Output is correct
2 Correct 144 ms 297552 KB Output is correct
3 Correct 113 ms 297556 KB Output is correct
4 Correct 112 ms 297556 KB Output is correct
5 Correct 108 ms 297560 KB Output is correct
6 Correct 108 ms 297556 KB Output is correct
7 Correct 115 ms 297208 KB Output is correct
8 Correct 109 ms 296784 KB Output is correct
9 Correct 106 ms 297556 KB Output is correct
10 Correct 113 ms 297560 KB Output is correct
11 Correct 108 ms 297552 KB Output is correct
12 Correct 112 ms 297556 KB Output is correct
13 Correct 102 ms 296324 KB Output is correct
14 Correct 104 ms 296532 KB Output is correct
15 Correct 104 ms 296528 KB Output is correct
16 Correct 95 ms 296416 KB Output is correct
17 Correct 97 ms 300388 KB Output is correct
18 Correct 104 ms 300372 KB Output is correct
19 Correct 107 ms 300368 KB Output is correct
20 Correct 107 ms 300116 KB Output is correct
21 Correct 103 ms 299940 KB Output is correct
22 Correct 99 ms 300116 KB Output is correct
23 Correct 105 ms 300192 KB Output is correct
24 Correct 103 ms 299228 KB Output is correct
25 Correct 127 ms 310608 KB Output is correct
26 Correct 106 ms 310500 KB Output is correct
27 Correct 106 ms 310616 KB Output is correct
28 Correct 101 ms 308812 KB Output is correct
29 Correct 110 ms 309332 KB Output is correct
30 Correct 117 ms 309332 KB Output is correct
31 Correct 116 ms 309208 KB Output is correct
32 Correct 110 ms 309076 KB Output is correct
33 Correct 174 ms 392788 KB Output is correct
34 Correct 160 ms 385196 KB Output is correct
35 Correct 176 ms 385104 KB Output is correct
36 Correct 657 ms 377556 KB Output is correct
37 Correct 193 ms 406760 KB Output is correct
38 Correct 181 ms 406528 KB Output is correct
39 Correct 192 ms 406612 KB Output is correct
40 Correct 187 ms 399704 KB Output is correct
41 Correct 186 ms 383784 KB Output is correct
42 Correct 195 ms 386384 KB Output is correct
43 Correct 249 ms 391252 KB Output is correct
44 Correct 230 ms 391508 KB Output is correct
45 Correct 168 ms 354388 KB Output is correct
46 Correct 176 ms 346764 KB Output is correct
47 Correct 231 ms 390228 KB Output is correct
48 Correct 230 ms 390228 KB Output is correct
49 Correct 104 ms 317916 KB Output is correct
50 Correct 101 ms 314804 KB Output is correct
51 Correct 107 ms 317776 KB Output is correct
52 Correct 104 ms 296384 KB Output is correct
53 Correct 110 ms 317776 KB Output is correct
54 Correct 107 ms 317908 KB Output is correct
55 Correct 108 ms 317872 KB Output is correct
56 Correct 107 ms 317776 KB Output is correct
57 Correct 109 ms 317776 KB Output is correct
58 Correct 105 ms 317164 KB Output is correct
59 Correct 98 ms 317520 KB Output is correct
60 Correct 98 ms 296528 KB Output is correct
61 Correct 560 ms 699588 KB Output is correct
62 Runtime error 785 ms 1048576 KB Execution killed with signal 9
63 Halted 0 ms 0 KB -