oj.uz

Submission #1009485

# Submission time Handle Problem Language Result Execution time Memory
1009485 2024-06-27T14:59:27 Z boris_mihov Rectangles (IOI19_rect) C++17
59 / 100
 870 ms 1048580 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];
std::vector <int> possibleColE[MAXN][MAXN];
std::vector <int> possibleRowE[MAXN][MAXN];

bool isOK(int rowB, int colB, int rowE, int colE)
{
    assert(rowB <= rowE);
    assert(colB <= 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);
    }

    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(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:139:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  139 |         while (st.size()) st.pop(); st.push(m + 1);
      |         ^~~~~
rect.cpp:139:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  139 |         while (st.size()) st.pop(); st.push(m + 1);
      |                                     ^~
rect.cpp:151:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  151 |         while (st.size()) st.pop(); st.push(0);
      |         ^~~~~
rect.cpp:151:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  151 |         while (st.size()) st.pop(); st.push(0);
      |                                     ^~
rect.cpp:166:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  166 |         while (st.size()) st.pop(); st.push(n + 1);
      |         ^~~~~
rect.cpp:166:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  166 |         while (st.size()) st.pop(); st.push(n + 1);
      |                                     ^~
rect.cpp:178:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  178 |         while (st.size()) st.pop(); st.push(0);
      |         ^~~~~
rect.cpp:178:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  178 |         while (st.size()) st.pop(); st.push(0);
      |                                     ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 296676 KB Output is correct
2 Correct 98 ms 299860 KB Output is correct
3 Correct 105 ms 299996 KB Output is correct
4 Correct 99 ms 299856 KB Output is correct
5 Correct 106 ms 299940 KB Output is correct
6 Correct 109 ms 299820 KB Output is correct
7 Correct 105 ms 298832 KB Output is correct
8 Correct 115 ms 298320 KB Output is correct
9 Correct 105 ms 299804 KB Output is correct
10 Correct 107 ms 299860 KB Output is correct
11 Correct 108 ms 300028 KB Output is correct
12 Correct 99 ms 299832 KB Output is correct
13 Correct 103 ms 296276 KB Output is correct
14 Correct 108 ms 296788 KB Output is correct
15 Correct 103 ms 297300 KB Output is correct
16 Correct 104 ms 296532 KB Output is correct
17 Correct 98 ms 296276 KB Output is correct
18 Correct 99 ms 296400 KB Output is correct
19 Correct 97 ms 299856 KB Output is correct
20 Correct 113 ms 298852 KB Output is correct
21 Correct 100 ms 296788 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 296676 KB Output is correct
2 Correct 98 ms 299860 KB Output is correct
3 Correct 105 ms 299996 KB Output is correct
4 Correct 99 ms 299856 KB Output is correct
5 Correct 106 ms 299940 KB Output is correct
6 Correct 109 ms 299820 KB Output is correct
7 Correct 105 ms 298832 KB Output is correct
8 Correct 115 ms 298320 KB Output is correct
9 Correct 105 ms 299804 KB Output is correct
10 Correct 107 ms 299860 KB Output is correct
11 Correct 108 ms 300028 KB Output is correct
12 Correct 99 ms 299832 KB Output is correct
13 Correct 103 ms 296276 KB Output is correct
14 Correct 108 ms 296788 KB Output is correct
15 Correct 103 ms 297300 KB Output is correct
16 Correct 104 ms 296532 KB Output is correct
17 Correct 98 ms 296276 KB Output is correct
18 Correct 99 ms 296400 KB Output is correct
19 Correct 97 ms 299856 KB Output is correct
20 Correct 113 ms 298852 KB Output is correct
21 Correct 100 ms 296788 KB Output is correct
22 Correct 105 ms 309472 KB Output is correct
23 Correct 117 ms 309328 KB Output is correct
24 Correct 109 ms 309400 KB Output is correct
25 Correct 101 ms 309076 KB Output is correct
26 Correct 103 ms 309076 KB Output is correct
27 Correct 107 ms 309076 KB Output is correct
28 Correct 128 ms 309108 KB Output is correct
29 Correct 104 ms 305368 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 296676 KB Output is correct
2 Correct 98 ms 299860 KB Output is correct
3 Correct 105 ms 299996 KB Output is correct
4 Correct 99 ms 299856 KB Output is correct
5 Correct 106 ms 299940 KB Output is correct
6 Correct 109 ms 299820 KB Output is correct
7 Correct 105 ms 298832 KB Output is correct
8 Correct 115 ms 298320 KB Output is correct
9 Correct 105 ms 299804 KB Output is correct
10 Correct 107 ms 299860 KB Output is correct
11 Correct 108 ms 300028 KB Output is correct
12 Correct 99 ms 299832 KB Output is correct
13 Correct 103 ms 296276 KB Output is correct
14 Correct 108 ms 296788 KB Output is correct
15 Correct 103 ms 297300 KB Output is correct
16 Correct 104 ms 296532 KB Output is correct
17 Correct 105 ms 309472 KB Output is correct
18 Correct 117 ms 309328 KB Output is correct
19 Correct 109 ms 309400 KB Output is correct
20 Correct 101 ms 309076 KB Output is correct
21 Correct 103 ms 309076 KB Output is correct
22 Correct 107 ms 309076 KB Output is correct
23 Correct 128 ms 309108 KB Output is correct
24 Correct 104 ms 305368 KB Output is correct
25 Correct 98 ms 296276 KB Output is correct
26 Correct 99 ms 296400 KB Output is correct
27 Correct 97 ms 299856 KB Output is correct
28 Correct 113 ms 298852 KB Output is correct
29 Correct 100 ms 296788 KB Output is correct
30 Correct 114 ms 337744 KB Output is correct
31 Correct 118 ms 337736 KB Output is correct
32 Correct 120 ms 337744 KB Output is correct
33 Correct 118 ms 336212 KB Output is correct
34 Correct 125 ms 336468 KB Output is correct
35 Correct 125 ms 336568 KB Output is correct
36 Correct 123 ms 336464 KB Output is correct
37 Correct 119 ms 336212 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 296676 KB Output is correct
2 Correct 98 ms 299860 KB Output is correct
3 Correct 105 ms 299996 KB Output is correct
4 Correct 99 ms 299856 KB Output is correct
5 Correct 106 ms 299940 KB Output is correct
6 Correct 109 ms 299820 KB Output is correct
7 Correct 105 ms 298832 KB Output is correct
8 Correct 115 ms 298320 KB Output is correct
9 Correct 105 ms 299804 KB Output is correct
10 Correct 107 ms 299860 KB Output is correct
11 Correct 108 ms 300028 KB Output is correct
12 Correct 99 ms 299832 KB Output is correct
13 Correct 103 ms 296276 KB Output is correct
14 Correct 108 ms 296788 KB Output is correct
15 Correct 103 ms 297300 KB Output is correct
16 Correct 104 ms 296532 KB Output is correct
17 Correct 105 ms 309472 KB Output is correct
18 Correct 117 ms 309328 KB Output is correct
19 Correct 109 ms 309400 KB Output is correct
20 Correct 101 ms 309076 KB Output is correct
21 Correct 103 ms 309076 KB Output is correct
22 Correct 107 ms 309076 KB Output is correct
23 Correct 128 ms 309108 KB Output is correct
24 Correct 104 ms 305368 KB Output is correct
25 Correct 114 ms 337744 KB Output is correct
26 Correct 118 ms 337736 KB Output is correct
27 Correct 120 ms 337744 KB Output is correct
28 Correct 118 ms 336212 KB Output is correct
29 Correct 125 ms 336468 KB Output is correct
30 Correct 125 ms 336568 KB Output is correct
31 Correct 123 ms 336464 KB Output is correct
32 Correct 119 ms 336212 KB Output is correct
33 Correct 98 ms 296276 KB Output is correct
34 Correct 99 ms 296400 KB Output is correct
35 Correct 97 ms 299856 KB Output is correct
36 Correct 113 ms 298852 KB Output is correct
37 Correct 100 ms 296788 KB Output is correct
38 Correct 233 ms 538960 KB Output is correct
39 Correct 215 ms 534356 KB Output is correct
40 Correct 224 ms 534352 KB Output is correct
41 Correct 870 ms 526928 KB Output is correct
42 Correct 249 ms 554576 KB Output is correct
43 Correct 240 ms 554320 KB Output is correct
44 Correct 241 ms 554832 KB Output is correct
45 Correct 236 ms 541720 KB Output is correct
46 Correct 258 ms 529488 KB Output is correct
47 Correct 252 ms 531936 KB Output is correct
48 Correct 318 ms 538400 KB Output is correct
49 Correct 308 ms 540168 KB Output is correct
50 Correct 215 ms 448848 KB Output is correct
51 Correct 204 ms 441676 KB Output is correct
52 Correct 330 ms 538048 KB Output is correct
53 Correct 315 ms 538964 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 358992 KB Output is correct
2 Correct 147 ms 349716 KB Output is correct
3 Correct 123 ms 358736 KB Output is correct
4 Correct 101 ms 296416 KB Output is correct
5 Correct 119 ms 358788 KB Output is correct
6 Correct 129 ms 358996 KB Output is correct
7 Correct 122 ms 358740 KB Output is correct
8 Correct 122 ms 358832 KB Output is correct
9 Correct 123 ms 358740 KB Output is correct
10 Correct 118 ms 338004 KB Output is correct
11 Correct 123 ms 358536 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 296276 KB Output is correct
2 Correct 99 ms 296400 KB Output is correct
3 Correct 97 ms 299856 KB Output is correct
4 Correct 113 ms 298852 KB Output is correct
5 Correct 100 ms 296788 KB Output is correct
6 Correct 126 ms 297296 KB Output is correct
7 Runtime error 632 ms 1048580 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 296676 KB Output is correct
2 Correct 98 ms 299860 KB Output is correct
3 Correct 105 ms 299996 KB Output is correct
4 Correct 99 ms 299856 KB Output is correct
5 Correct 106 ms 299940 KB Output is correct
6 Correct 109 ms 299820 KB Output is correct
7 Correct 105 ms 298832 KB Output is correct
8 Correct 115 ms 298320 KB Output is correct
9 Correct 105 ms 299804 KB Output is correct
10 Correct 107 ms 299860 KB Output is correct
11 Correct 108 ms 300028 KB Output is correct
12 Correct 99 ms 299832 KB Output is correct
13 Correct 103 ms 296276 KB Output is correct
14 Correct 108 ms 296788 KB Output is correct
15 Correct 103 ms 297300 KB Output is correct
16 Correct 104 ms 296532 KB Output is correct
17 Correct 105 ms 309472 KB Output is correct
18 Correct 117 ms 309328 KB Output is correct
19 Correct 109 ms 309400 KB Output is correct
20 Correct 101 ms 309076 KB Output is correct
21 Correct 103 ms 309076 KB Output is correct
22 Correct 107 ms 309076 KB Output is correct
23 Correct 128 ms 309108 KB Output is correct
24 Correct 104 ms 305368 KB Output is correct
25 Correct 114 ms 337744 KB Output is correct
26 Correct 118 ms 337736 KB Output is correct
27 Correct 120 ms 337744 KB Output is correct
28 Correct 118 ms 336212 KB Output is correct
29 Correct 125 ms 336468 KB Output is correct
30 Correct 125 ms 336568 KB Output is correct
31 Correct 123 ms 336464 KB Output is correct
32 Correct 119 ms 336212 KB Output is correct
33 Correct 233 ms 538960 KB Output is correct
34 Correct 215 ms 534356 KB Output is correct
35 Correct 224 ms 534352 KB Output is correct
36 Correct 870 ms 526928 KB Output is correct
37 Correct 249 ms 554576 KB Output is correct
38 Correct 240 ms 554320 KB Output is correct
39 Correct 241 ms 554832 KB Output is correct
40 Correct 236 ms 541720 KB Output is correct
41 Correct 258 ms 529488 KB Output is correct
42 Correct 252 ms 531936 KB Output is correct
43 Correct 318 ms 538400 KB Output is correct
44 Correct 308 ms 540168 KB Output is correct
45 Correct 215 ms 448848 KB Output is correct
46 Correct 204 ms 441676 KB Output is correct
47 Correct 330 ms 538048 KB Output is correct
48 Correct 315 ms 538964 KB Output is correct
49 Correct 119 ms 358992 KB Output is correct
50 Correct 147 ms 349716 KB Output is correct
51 Correct 123 ms 358736 KB Output is correct
52 Correct 101 ms 296416 KB Output is correct
53 Correct 119 ms 358788 KB Output is correct
54 Correct 129 ms 358996 KB Output is correct
55 Correct 122 ms 358740 KB Output is correct
56 Correct 122 ms 358832 KB Output is correct
57 Correct 123 ms 358740 KB Output is correct
58 Correct 118 ms 338004 KB Output is correct
59 Correct 123 ms 358536 KB Output is correct
60 Correct 126 ms 297296 KB Output is correct
61 Runtime error 632 ms 1048580 KB Execution killed with signal 9
62 Halted 0 ms 0 KB -