oj.uz

Submission #1009552

# Submission time Handle Problem Language Result Execution time Memory
1009552 2024-06-27T15:40:19 Z boris_mihov Rectangles (IOI19_rect) C++17
59 / 100
 1360 ms 1048576 KB 
#include "rect.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>
 
typedef long long llong;
const short MAXLOG = 12;
const short MAXN = 2500 + 10;
const int INF  = 1e8;
 
short n, m;
short getLOG[MAXN];
struct SparseMIN
{
    short sparse[MAXN][MAXLOG];
    short len;
 
    void build(short a[], short length)
    {
        len = length;
        for (short i = 1 ; i <= len ; ++i)
        {
            sparse[i][0] = a[i]; 
        }
 
        for (short lg = 1 ; (1 << lg) <= len ; ++lg)
        {
            for (short i = 1 ; i + (1 << lg) - 1 <= len ; ++i)
            {
                sparse[i][lg] = std::min(sparse[i][lg - 1], sparse[i + (1 << lg - 1)][lg - 1]);
            }
        }
    }
 
    short findMIN(short &l, short &r, short &val)
    {
        short lg = getLOG[r - l + 1];
        if (sparse[l][lg] < val) return false;
        if (sparse[r - (1 << lg) + 1][lg] < val) return false;
        return true;
    }
};
 
struct SparseMAX
{
    short sparse[MAXN][MAXLOG];
    short len;
 
    void build(short a[], short length)
    {
        len = length;
        for (short i = 1 ; i <= len ; ++i)
        {
            sparse[i][0] = a[i]; 
        }
 
        for (short lg = 1 ; (1 << lg) <= len ; ++lg)
        {
            for (short i = 1 ; i + (1 << lg) - 1 <= len ; ++i)
            {
                sparse[i][lg] = std::max(sparse[i][lg - 1], sparse[i + (1 << lg - 1)][lg - 1]);
            }
        }
    }
 
    bool findMAX(short &l, short &r, short &val)
    {
        short lg = getLOG[r - l + 1];
        if (sparse[l][lg] > val) return false;
        if (sparse[r - (1 << lg) + 1][lg] > val) return false;
        return true;
    }
};
 
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(short &rowB, short &colB, short &rowE, short &colE)
{
    bool result = true;
    colB++; colE--;
    if (result && !sparseRD[rowB].findMIN(colB, colE, rowE)) result = false;
    if (result && !sparseRU[rowE].findMAX(colB, colE, rowB)) result = false;
    colB--; colE++;
    rowE--; rowB++;
    if (result && !sparseCL[colB].findMIN(rowB, rowE, colE)) result = false;
    if (result && !sparseCR[colE].findMAX(rowB, rowE, colB)) result = false;
    rowE++; rowB--;
    return result;
}
 
llong count_rectangles(std::vector <std::vector<int>> _a)
{
    n = _a.size(); m = _a[0].size();
    for (short i = 0 ; i < n ; ++i)
    {
        for (short j = 0 ; j < m ; ++j)
        {
            t[i + 1][j + 1] = _a[i][j];
        }
    }
 
    for (short i = 0 ; i <= n + 1 ; ++i)
    {
        t[i][0] = t[i][m + 1] = INF;
    }
 
    for (short i = 0 ; i <= m + 1 ; ++i)
    {
        t[0][i] = t[n + 1][i] = INF;
    }
 
    std::stack <short> st;
    for (short i = 1 ; i <= n ; ++i)
    {
        while (st.size()) st.pop(); st.push(m + 1);
        for (short 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 (short j = 1 ; j <= m ; ++j)
        {
            while (t[i][j] > t[i][st.top()])
            {
                st.pop();
            }
 
            c[i][j] = st.top();
            st.push(j);
        }
    }
 
    for (short i = 1 ; i <= m ; ++i)
    {
        while (st.size()) st.pop(); st.push(n + 1);
        for (short 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 (short j = 1 ; j <= n ; ++j)
        {
            while (t[j][i] > t[st.top()][i])
            {
                st.pop();
            }
 
            d[j][i] = st.top();
            st.push(j);
        }
    }
 
    for (short i = 1 ; i <= std::max(n, m) ; ++i)
    {
        getLOG[i] = getLOG[i - 1];
        if ((1 << getLOG[i] + 1) < i) getLOG[i]++;
    }
 
    for (short i = 1 ; i <= n ; ++i)
    {
        sparseRD[i].build(b[i], m);
        sparseRU[i].build(d[i], m);
    }
 
    for (short i = 1 ; i <= m ; ++i)
    {
        for (short j = 1 ; j <= n ; ++j)
        {
            cpy[j] = a[j][i];
        }
 
        sparseCL[i].build(cpy, n);
 
        for (short j = 1 ; j <= n ; ++j)
        {
            cpy[j] = c[j][i];
        }
 
        sparseCR[i].build(cpy, n);
    }
 
    for (short i = 2 ; i <= n ; ++i)
    {
        for (short j = 2 ; j <= m ; ++j)
        {
            if (d[i][j] < i - 1) possibleRowE[d[i][j]][j - 1].push_back(i);
            if (c[i][j] < j - 1) possibleColE[i - 1][c[i][j]].push_back(j);
        }
    }
 
    for (short i = 2 ; i <= n ; ++i)
    {
        for (short j = 2 ; j <= m ; ++j)
        {
            if (i < b[i - 1][j] && b[i - 1][j] != n + 1 && (possibleRowE[i - 1][j - 1].empty() || possibleRowE[i - 1][j - 1].back() != b[i - 1][j])) possibleRowE[i - 1][j - 1].push_back(b[i - 1][j]);
            if (j < a[i][j - 1] && a[i][j - 1] != m + 1 && (possibleColE[i - 1][j - 1].empty() || possibleColE[i - 1][j - 1].back() != a[i][j - 1])) possibleColE[i - 1][j - 1].push_back(a[i][j - 1]);
        }
    }
 
    int answer = 0;
    for (short rowB = 1 ; rowB + 1 < n ; ++rowB)
    {
        for (short colB = 1 ; colB + 1 < m ; ++colB)
        {
            for (short &rowE : possibleRowE[rowB][colB])
            {
                for (short &colE : possibleColE[rowB][colB])
                {
                    answer += isOK(rowB, colB, rowE, colE);
                }
            }
        }
    }
 
    return answer;
}

Compilation message

rect.cpp: In member function 'void SparseMIN::build(short int*, short 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*, short int)':
rect.cpp:64:81: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   64 |                 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:130:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  130 |         while (st.size()) st.pop(); st.push(m + 1);
      |         ^~~~~
rect.cpp:130:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  130 |         while (st.size()) st.pop(); st.push(m + 1);
      |                                     ^~
rect.cpp:142:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  142 |         while (st.size()) st.pop(); st.push(0);
      |         ^~~~~
rect.cpp:142:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  142 |         while (st.size()) st.pop(); st.push(0);
      |                                     ^~
rect.cpp:157:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  157 |         while (st.size()) st.pop(); st.push(n + 1);
      |         ^~~~~
rect.cpp:157:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  157 |         while (st.size()) st.pop(); st.push(n + 1);
      |                                     ^~
rect.cpp:169:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  169 |         while (st.size()) st.pop(); st.push(0);
      |         ^~~~~
rect.cpp:169:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  169 |         while (st.size()) st.pop(); st.push(0);
      |                                     ^~
rect.cpp:185:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  185 |         if ((1 << getLOG[i] + 1) < i) getLOG[i]++;
      |                   ~~~~~~~~~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 296528 KB Output is correct
2 Correct 106 ms 297556 KB Output is correct
3 Correct 110 ms 297484 KB Output is correct
4 Correct 105 ms 297556 KB Output is correct
5 Correct 101 ms 297552 KB Output is correct
6 Correct 105 ms 297520 KB Output is correct
7 Correct 95 ms 297336 KB Output is correct
8 Correct 96 ms 296812 KB Output is correct
9 Correct 101 ms 297600 KB Output is correct
10 Correct 104 ms 297504 KB Output is correct
11 Correct 102 ms 297552 KB Output is correct
12 Correct 97 ms 297388 KB Output is correct
13 Correct 105 ms 296388 KB Output is correct
14 Correct 100 ms 296544 KB Output is correct
15 Correct 102 ms 296532 KB Output is correct
16 Correct 103 ms 296272 KB Output is correct
17 Correct 106 ms 296276 KB Output is correct
18 Correct 99 ms 296276 KB Output is correct
19 Correct 106 ms 297556 KB Output is correct
20 Correct 107 ms 297296 KB Output is correct
21 Correct 105 ms 296528 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 296528 KB Output is correct
2 Correct 106 ms 297556 KB Output is correct
3 Correct 110 ms 297484 KB Output is correct
4 Correct 105 ms 297556 KB Output is correct
5 Correct 101 ms 297552 KB Output is correct
6 Correct 105 ms 297520 KB Output is correct
7 Correct 95 ms 297336 KB Output is correct
8 Correct 96 ms 296812 KB Output is correct
9 Correct 101 ms 297600 KB Output is correct
10 Correct 104 ms 297504 KB Output is correct
11 Correct 102 ms 297552 KB Output is correct
12 Correct 97 ms 297388 KB Output is correct
13 Correct 105 ms 296388 KB Output is correct
14 Correct 100 ms 296544 KB Output is correct
15 Correct 102 ms 296532 KB Output is correct
16 Correct 103 ms 296272 KB Output is correct
17 Correct 106 ms 296276 KB Output is correct
18 Correct 99 ms 296276 KB Output is correct
19 Correct 106 ms 297556 KB Output is correct
20 Correct 107 ms 297296 KB Output is correct
21 Correct 105 ms 296528 KB Output is correct
22 Correct 106 ms 300368 KB Output is correct
23 Correct 106 ms 300192 KB Output is correct
24 Correct 115 ms 300376 KB Output is correct
25 Correct 110 ms 299992 KB Output is correct
26 Correct 107 ms 299920 KB Output is correct
27 Correct 118 ms 300108 KB Output is correct
28 Correct 103 ms 300112 KB Output is correct
29 Correct 101 ms 299240 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 296528 KB Output is correct
2 Correct 106 ms 297556 KB Output is correct
3 Correct 110 ms 297484 KB Output is correct
4 Correct 105 ms 297556 KB Output is correct
5 Correct 101 ms 297552 KB Output is correct
6 Correct 105 ms 297520 KB Output is correct
7 Correct 95 ms 297336 KB Output is correct
8 Correct 96 ms 296812 KB Output is correct
9 Correct 101 ms 297600 KB Output is correct
10 Correct 104 ms 297504 KB Output is correct
11 Correct 102 ms 297552 KB Output is correct
12 Correct 97 ms 297388 KB Output is correct
13 Correct 105 ms 296388 KB Output is correct
14 Correct 100 ms 296544 KB Output is correct
15 Correct 102 ms 296532 KB Output is correct
16 Correct 103 ms 296272 KB Output is correct
17 Correct 106 ms 300368 KB Output is correct
18 Correct 106 ms 300192 KB Output is correct
19 Correct 115 ms 300376 KB Output is correct
20 Correct 110 ms 299992 KB Output is correct
21 Correct 107 ms 299920 KB Output is correct
22 Correct 118 ms 300108 KB Output is correct
23 Correct 103 ms 300112 KB Output is correct
24 Correct 101 ms 299240 KB Output is correct
25 Correct 106 ms 296276 KB Output is correct
26 Correct 99 ms 296276 KB Output is correct
27 Correct 106 ms 297556 KB Output is correct
28 Correct 107 ms 297296 KB Output is correct
29 Correct 105 ms 296528 KB Output is correct
30 Correct 117 ms 310612 KB Output is correct
31 Correct 125 ms 310612 KB Output is correct
32 Correct 112 ms 310612 KB Output is correct
33 Correct 122 ms 309060 KB Output is correct
34 Correct 120 ms 309464 KB Output is correct
35 Correct 125 ms 309452 KB Output is correct
36 Correct 133 ms 309148 KB Output is correct
37 Correct 124 ms 309128 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 296528 KB Output is correct
2 Correct 106 ms 297556 KB Output is correct
3 Correct 110 ms 297484 KB Output is correct
4 Correct 105 ms 297556 KB Output is correct
5 Correct 101 ms 297552 KB Output is correct
6 Correct 105 ms 297520 KB Output is correct
7 Correct 95 ms 297336 KB Output is correct
8 Correct 96 ms 296812 KB Output is correct
9 Correct 101 ms 297600 KB Output is correct
10 Correct 104 ms 297504 KB Output is correct
11 Correct 102 ms 297552 KB Output is correct
12 Correct 97 ms 297388 KB Output is correct
13 Correct 105 ms 296388 KB Output is correct
14 Correct 100 ms 296544 KB Output is correct
15 Correct 102 ms 296532 KB Output is correct
16 Correct 103 ms 296272 KB Output is correct
17 Correct 106 ms 300368 KB Output is correct
18 Correct 106 ms 300192 KB Output is correct
19 Correct 115 ms 300376 KB Output is correct
20 Correct 110 ms 299992 KB Output is correct
21 Correct 107 ms 299920 KB Output is correct
22 Correct 118 ms 300108 KB Output is correct
23 Correct 103 ms 300112 KB Output is correct
24 Correct 101 ms 299240 KB Output is correct
25 Correct 117 ms 310612 KB Output is correct
26 Correct 125 ms 310612 KB Output is correct
27 Correct 112 ms 310612 KB Output is correct
28 Correct 122 ms 309060 KB Output is correct
29 Correct 120 ms 309464 KB Output is correct
30 Correct 125 ms 309452 KB Output is correct
31 Correct 133 ms 309148 KB Output is correct
32 Correct 124 ms 309128 KB Output is correct
33 Correct 106 ms 296276 KB Output is correct
34 Correct 99 ms 296276 KB Output is correct
35 Correct 106 ms 297556 KB Output is correct
36 Correct 107 ms 297296 KB Output is correct
37 Correct 105 ms 296528 KB Output is correct
38 Correct 221 ms 392944 KB Output is correct
39 Correct 199 ms 385204 KB Output is correct
40 Correct 216 ms 385108 KB Output is correct
41 Correct 1360 ms 377676 KB Output is correct
42 Correct 259 ms 406612 KB Output is correct
43 Correct 227 ms 406488 KB Output is correct
44 Correct 231 ms 406608 KB Output is correct
45 Correct 238 ms 399836 KB Output is correct
46 Correct 220 ms 383828 KB Output is correct
47 Correct 231 ms 386388 KB Output is correct
48 Correct 286 ms 391252 KB Output is correct
49 Correct 282 ms 391508 KB Output is correct
50 Correct 187 ms 354352 KB Output is correct
51 Correct 180 ms 346612 KB Output is correct
52 Correct 266 ms 390032 KB Output is correct
53 Correct 250 ms 390228 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 318032 KB Output is correct
2 Correct 110 ms 314708 KB Output is correct
3 Correct 111 ms 317612 KB Output is correct
4 Correct 104 ms 296480 KB Output is correct
5 Correct 111 ms 317752 KB Output is correct
6 Correct 120 ms 317780 KB Output is correct
7 Correct 112 ms 317780 KB Output is correct
8 Correct 113 ms 317980 KB Output is correct
9 Correct 114 ms 317780 KB Output is correct
10 Correct 114 ms 317244 KB Output is correct
11 Correct 117 ms 317520 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 296276 KB Output is correct
2 Correct 99 ms 296276 KB Output is correct
3 Correct 106 ms 297556 KB Output is correct
4 Correct 107 ms 297296 KB Output is correct
5 Correct 105 ms 296528 KB Output is correct
6 Correct 108 ms 296560 KB Output is correct
7 Correct 692 ms 697672 KB Output is correct
8 Runtime error 999 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 99 ms 296528 KB Output is correct
2 Correct 106 ms 297556 KB Output is correct
3 Correct 110 ms 297484 KB Output is correct
4 Correct 105 ms 297556 KB Output is correct
5 Correct 101 ms 297552 KB Output is correct
6 Correct 105 ms 297520 KB Output is correct
7 Correct 95 ms 297336 KB Output is correct
8 Correct 96 ms 296812 KB Output is correct
9 Correct 101 ms 297600 KB Output is correct
10 Correct 104 ms 297504 KB Output is correct
11 Correct 102 ms 297552 KB Output is correct
12 Correct 97 ms 297388 KB Output is correct
13 Correct 105 ms 296388 KB Output is correct
14 Correct 100 ms 296544 KB Output is correct
15 Correct 102 ms 296532 KB Output is correct
16 Correct 103 ms 296272 KB Output is correct
17 Correct 106 ms 300368 KB Output is correct
18 Correct 106 ms 300192 KB Output is correct
19 Correct 115 ms 300376 KB Output is correct
20 Correct 110 ms 299992 KB Output is correct
21 Correct 107 ms 299920 KB Output is correct
22 Correct 118 ms 300108 KB Output is correct
23 Correct 103 ms 300112 KB Output is correct
24 Correct 101 ms 299240 KB Output is correct
25 Correct 117 ms 310612 KB Output is correct
26 Correct 125 ms 310612 KB Output is correct
27 Correct 112 ms 310612 KB Output is correct
28 Correct 122 ms 309060 KB Output is correct
29 Correct 120 ms 309464 KB Output is correct
30 Correct 125 ms 309452 KB Output is correct
31 Correct 133 ms 309148 KB Output is correct
32 Correct 124 ms 309128 KB Output is correct
33 Correct 221 ms 392944 KB Output is correct
34 Correct 199 ms 385204 KB Output is correct
35 Correct 216 ms 385108 KB Output is correct
36 Correct 1360 ms 377676 KB Output is correct
37 Correct 259 ms 406612 KB Output is correct
38 Correct 227 ms 406488 KB Output is correct
39 Correct 231 ms 406608 KB Output is correct
40 Correct 238 ms 399836 KB Output is correct
41 Correct 220 ms 383828 KB Output is correct
42 Correct 231 ms 386388 KB Output is correct
43 Correct 286 ms 391252 KB Output is correct
44 Correct 282 ms 391508 KB Output is correct
45 Correct 187 ms 354352 KB Output is correct
46 Correct 180 ms 346612 KB Output is correct
47 Correct 266 ms 390032 KB Output is correct
48 Correct 250 ms 390228 KB Output is correct
49 Correct 115 ms 318032 KB Output is correct
50 Correct 110 ms 314708 KB Output is correct
51 Correct 111 ms 317612 KB Output is correct
52 Correct 104 ms 296480 KB Output is correct
53 Correct 111 ms 317752 KB Output is correct
54 Correct 120 ms 317780 KB Output is correct
55 Correct 112 ms 317780 KB Output is correct
56 Correct 113 ms 317980 KB Output is correct
57 Correct 114 ms 317780 KB Output is correct
58 Correct 114 ms 317244 KB Output is correct
59 Correct 117 ms 317520 KB Output is correct
60 Correct 108 ms 296560 KB Output is correct
61 Correct 692 ms 697672 KB Output is correct
62 Runtime error 999 ms 1048576 KB Execution killed with signal 9
63 Halted 0 ms 0 KB -