oj.uz

Submission #1009462

# Submission time Handle Problem Language Result Execution time Memory
1009462 2024-06-27T14:36:10 Z boris_mihov Rectangles (IOI19_rect) C++17
37 / 100
 5000 ms 853292 KB 
#include "rect.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>

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

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

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

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

        for (int i = 1 ; i <= len ; ++i)
        {
            getLOG[i] = getLOG[i - 1];
            if ((1 << getLOG[i] + 1) < i) getLOG[i]++;
        }
    }

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

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

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

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

        for (int i = 1 ; i <= len ; ++i)
        {
            getLOG[i] = getLOG[i - 1];
            if ((1 << getLOG[i] + 1) < i) getLOG[i]++;
        }
    }

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

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

SparseMIN sparseRD[MAXN];
SparseMAX sparseRU[MAXN];
SparseMIN sparseCL[MAXN];
SparseMAX sparseCR[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 <= 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);
    }

    int answer = 0;
    for (int rowB = 2 ; rowB < n ; ++rowB)
    {
        for (int colB = 2 ; colB < m ; ++colB)
        {
            for (int rowE = rowB ; rowE < n ; ++rowE)
            {
                for (int colE = colB ; colE < m ; ++colE)
                {
                    answer += isOK(rowB, colB, rowE, colE);
                }
            }
        }
    }

    return answer;
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 20824 KB Output is correct
2 Correct 5 ms 43352 KB Output is correct
3 Correct 5 ms 43476 KB Output is correct
4 Correct 6 ms 43356 KB Output is correct
5 Correct 6 ms 43356 KB Output is correct
6 Correct 5 ms 43356 KB Output is correct
7 Correct 4 ms 39260 KB Output is correct
8 Correct 3 ms 29020 KB Output is correct
9 Correct 6 ms 43660 KB Output is correct
10 Correct 5 ms 43352 KB Output is correct
11 Correct 5 ms 43556 KB Output is correct
12 Correct 5 ms 43356 KB Output is correct
13 Correct 2 ms 18776 KB Output is correct
14 Correct 2 ms 22876 KB Output is correct
15 Correct 3 ms 22876 KB Output is correct
16 Correct 2 ms 18780 KB Output is correct
17 Correct 2 ms 18872 KB Output is correct
18 Correct 2 ms 18880 KB Output is correct
19 Correct 5 ms 43356 KB Output is correct
20 Correct 5 ms 39416 KB Output is correct
21 Correct 2 ms 22876 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 20824 KB Output is correct
2 Correct 5 ms 43352 KB Output is correct
3 Correct 5 ms 43476 KB Output is correct
4 Correct 6 ms 43356 KB Output is correct
5 Correct 6 ms 43356 KB Output is correct
6 Correct 5 ms 43356 KB Output is correct
7 Correct 4 ms 39260 KB Output is correct
8 Correct 3 ms 29020 KB Output is correct
9 Correct 6 ms 43660 KB Output is correct
10 Correct 5 ms 43352 KB Output is correct
11 Correct 5 ms 43556 KB Output is correct
12 Correct 5 ms 43356 KB Output is correct
13 Correct 2 ms 18776 KB Output is correct
14 Correct 2 ms 22876 KB Output is correct
15 Correct 3 ms 22876 KB Output is correct
16 Correct 2 ms 18780 KB Output is correct
17 Correct 2 ms 18872 KB Output is correct
18 Correct 2 ms 18880 KB Output is correct
19 Correct 5 ms 43356 KB Output is correct
20 Correct 5 ms 39416 KB Output is correct
21 Correct 2 ms 22876 KB Output is correct
22 Correct 67 ms 72340 KB Output is correct
23 Correct 84 ms 72284 KB Output is correct
24 Correct 64 ms 72280 KB Output is correct
25 Correct 43 ms 72284 KB Output is correct
26 Correct 44 ms 70152 KB Output is correct
27 Correct 43 ms 72284 KB Output is correct
28 Correct 44 ms 72284 KB Output is correct
29 Correct 18 ms 59992 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 20824 KB Output is correct
2 Correct 5 ms 43352 KB Output is correct
3 Correct 5 ms 43476 KB Output is correct
4 Correct 6 ms 43356 KB Output is correct
5 Correct 6 ms 43356 KB Output is correct
6 Correct 5 ms 43356 KB Output is correct
7 Correct 4 ms 39260 KB Output is correct
8 Correct 3 ms 29020 KB Output is correct
9 Correct 6 ms 43660 KB Output is correct
10 Correct 5 ms 43352 KB Output is correct
11 Correct 5 ms 43556 KB Output is correct
12 Correct 5 ms 43356 KB Output is correct
13 Correct 2 ms 18776 KB Output is correct
14 Correct 2 ms 22876 KB Output is correct
15 Correct 3 ms 22876 KB Output is correct
16 Correct 2 ms 18780 KB Output is correct
17 Correct 67 ms 72340 KB Output is correct
18 Correct 84 ms 72284 KB Output is correct
19 Correct 64 ms 72280 KB Output is correct
20 Correct 43 ms 72284 KB Output is correct
21 Correct 44 ms 70152 KB Output is correct
22 Correct 43 ms 72284 KB Output is correct
23 Correct 44 ms 72284 KB Output is correct
24 Correct 18 ms 59992 KB Output is correct
25 Correct 2 ms 18872 KB Output is correct
26 Correct 2 ms 18880 KB Output is correct
27 Correct 5 ms 43356 KB Output is correct
28 Correct 5 ms 39416 KB Output is correct
29 Correct 2 ms 22876 KB Output is correct
30 Correct 2268 ms 92924 KB Output is correct
31 Correct 2352 ms 92764 KB Output is correct
32 Correct 2553 ms 93888 KB Output is correct
33 Correct 1470 ms 92764 KB Output is correct
34 Correct 1430 ms 94336 KB Output is correct
35 Correct 1420 ms 93080 KB Output is correct
36 Correct 1351 ms 93044 KB Output is correct
37 Correct 1389 ms 94044 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 20824 KB Output is correct
2 Correct 5 ms 43352 KB Output is correct
3 Correct 5 ms 43476 KB Output is correct
4 Correct 6 ms 43356 KB Output is correct
5 Correct 6 ms 43356 KB Output is correct
6 Correct 5 ms 43356 KB Output is correct
7 Correct 4 ms 39260 KB Output is correct
8 Correct 3 ms 29020 KB Output is correct
9 Correct 6 ms 43660 KB Output is correct
10 Correct 5 ms 43352 KB Output is correct
11 Correct 5 ms 43556 KB Output is correct
12 Correct 5 ms 43356 KB Output is correct
13 Correct 2 ms 18776 KB Output is correct
14 Correct 2 ms 22876 KB Output is correct
15 Correct 3 ms 22876 KB Output is correct
16 Correct 2 ms 18780 KB Output is correct
17 Correct 67 ms 72340 KB Output is correct
18 Correct 84 ms 72284 KB Output is correct
19 Correct 64 ms 72280 KB Output is correct
20 Correct 43 ms 72284 KB Output is correct
21 Correct 44 ms 70152 KB Output is correct
22 Correct 43 ms 72284 KB Output is correct
23 Correct 44 ms 72284 KB Output is correct
24 Correct 18 ms 59992 KB Output is correct
25 Correct 2268 ms 92924 KB Output is correct
26 Correct 2352 ms 92764 KB Output is correct
27 Correct 2553 ms 93888 KB Output is correct
28 Correct 1470 ms 92764 KB Output is correct
29 Correct 1430 ms 94336 KB Output is correct
30 Correct 1420 ms 93080 KB Output is correct
31 Correct 1351 ms 93044 KB Output is correct
32 Correct 1389 ms 94044 KB Output is correct
33 Correct 2 ms 18872 KB Output is correct
34 Correct 2 ms 18880 KB Output is correct
35 Correct 5 ms 43356 KB Output is correct
36 Correct 5 ms 39416 KB Output is correct
37 Correct 2 ms 22876 KB Output is correct
38 Execution timed out 5062 ms 268120 KB Time limit exceeded
39 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 132436 KB Output is correct
2 Correct 54 ms 121168 KB Output is correct
3 Correct 42 ms 130468 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 43 ms 132444 KB Output is correct
6 Correct 43 ms 130548 KB Output is correct
7 Correct 44 ms 130388 KB Output is correct
8 Correct 45 ms 132432 KB Output is correct
9 Correct 44 ms 130384 KB Output is correct
10 Correct 24 ms 114004 KB Output is correct
11 Correct 31 ms 130384 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18872 KB Output is correct
2 Correct 2 ms 18880 KB Output is correct
3 Correct 5 ms 43356 KB Output is correct
4 Correct 5 ms 39416 KB Output is correct
5 Correct 2 ms 22876 KB Output is correct
6 Correct 3 ms 22876 KB Output is correct
7 Execution timed out 5112 ms 853292 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 20824 KB Output is correct
2 Correct 5 ms 43352 KB Output is correct
3 Correct 5 ms 43476 KB Output is correct
4 Correct 6 ms 43356 KB Output is correct
5 Correct 6 ms 43356 KB Output is correct
6 Correct 5 ms 43356 KB Output is correct
7 Correct 4 ms 39260 KB Output is correct
8 Correct 3 ms 29020 KB Output is correct
9 Correct 6 ms 43660 KB Output is correct
10 Correct 5 ms 43352 KB Output is correct
11 Correct 5 ms 43556 KB Output is correct
12 Correct 5 ms 43356 KB Output is correct
13 Correct 2 ms 18776 KB Output is correct
14 Correct 2 ms 22876 KB Output is correct
15 Correct 3 ms 22876 KB Output is correct
16 Correct 2 ms 18780 KB Output is correct
17 Correct 67 ms 72340 KB Output is correct
18 Correct 84 ms 72284 KB Output is correct
19 Correct 64 ms 72280 KB Output is correct
20 Correct 43 ms 72284 KB Output is correct
21 Correct 44 ms 70152 KB Output is correct
22 Correct 43 ms 72284 KB Output is correct
23 Correct 44 ms 72284 KB Output is correct
24 Correct 18 ms 59992 KB Output is correct
25 Correct 2268 ms 92924 KB Output is correct
26 Correct 2352 ms 92764 KB Output is correct
27 Correct 2553 ms 93888 KB Output is correct
28 Correct 1470 ms 92764 KB Output is correct
29 Correct 1430 ms 94336 KB Output is correct
30 Correct 1420 ms 93080 KB Output is correct
31 Correct 1351 ms 93044 KB Output is correct
32 Correct 1389 ms 94044 KB Output is correct
33 Execution timed out 5062 ms 268120 KB Time limit exceeded
34 Halted 0 ms 0 KB -