# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
987292 |
2024-05-22T14:03:09 Z |
cig32 |
Rectangles (IOI19_rect) |
C++17 |
|
5000 ms |
471048 KB |
#include "rect.h"
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 2500;
int32_t upBad[MAXN][MAXN];
int32_t downBad[MAXN][MAXN];
int32_t leftBad[MAXN][MAXN];
int32_t rightBad[MAXN][MAXN];
int32_t up[MAXN][12][MAXN], down[MAXN][12][MAXN];
int32_t Left[MAXN][12][MAXN], Right[MAXN][12][MAXN];
int n,m;
int32_t dsu[MAXN * MAXN];
int set_of(int u) {
if(dsu[u] == u) return u;
return dsu[u] = set_of(dsu[u]);
}
void union_(int u, int v) {
dsu[set_of(u)] = set_of(v);
}
int up_query(int i, int l, int r) {
int k = 32 - __builtin_clz(r - l + 1) - 1;
return max(up[i][k][l], up[i][k][r - (1<<k) + 1]);
}
int down_query(int i, int l, int r) {
int k = 32 - __builtin_clz(r - l + 1) - 1;
return min(down[i][k][l], down[i][k][r - (1<<k) + 1]);
}
int left_query(int i, int l, int r) {
int k = 32 - __builtin_clz(r - l + 1) - 1;
return max(Left[i][k][l], Left[i][k][r - (1<<k) + 1]);
}
int right_query(int i, int l, int r) {
int k = 32 - __builtin_clz(r - l + 1) - 1;
return min(Right[i][k][l], Right[i][k][r - (1<<k) + 1]);
}
int count_rectangles(std::vector<std::vector<int32_t> > a) {
n = a.size(), m = a[0].size();
int32_t mx = 0;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
mx = max(mx, a[i][j]);
dsu[i * m + j] = i * m + j;
rightBad[i][j] = m;
downBad[i][j] = n;
upBad[i][j] = -1;
leftBad[i][j] = -1;
for(int k=j+1; k<m; k++) {
if(a[i][k] >= a[i][j]) {
rightBad[i][j] = k; break;
}
}
for(int k=j-1; k>=0; k--) {
if(a[i][k] >= a[i][j]) {
leftBad[i][j] = k; break;
}
}
for(int k=i+1; k<n; k++) {
if(a[k][j] >= a[i][j]) {
downBad[i][j] = k; break;
}
}
for(int k=i-1; k>=0; k--) {
if(a[k][j] >= a[i][j]) {
upBad[i][j] = k; break;
}
}
}
}
if(mx == 1) {
for(int i=0; i+1<n; i++) {
for(int j=0; j+1<m; j++) {
if(a[i][j] == 0 && a[i][j+1] == 0) union_(i*m + j, i*m + j + 1);
if(a[i][j] == 0 && a[i+1][j] == 0) union_(i*m + j, (i+1)*m + j);
}
}
vector<int> ll[n * m];
for(int i=0; i<n*m; i++) ll[set_of(i)].push_back(i);
int ans = 0;
for(int i=0; i<n*m; i++) {
if(ll[i].size()) {
int r = ll[i][0] / m, c = ll[i][0] % m;
if(a[r][c] == 1) continue;
int u, d, l;
u = l = 1e9, d = r = -1;
for(int x: ll[i]) {
u = min(u, x / m);
d = max(d, x / m);
l = min(l, x % m);
r = max(r, x % m);
}
if((d - u + 1) * (r - l + 1) == ll[i].size() && u > 0 && l > 0 && d + 1 < n && r + 1 < m) {
ans++;
}
}
}
return ans;
}
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
Left[j][0][i] = leftBad[i][j];
Right[j][0][i] = rightBad[i][j];
up[i][0][j] = upBad[i][j];
down[i][0][j] = downBad[i][j];
}
}
for(int k=1; k<12; k++) {
for(int i=0; i<n; i++) {
for(int j=0; j+(1<<k)-1<m; j++) {
up[i][k][j] = max(up[i][k-1][j], up[i][k-1][j+(1<<(k-1))]);
down[i][k][j] = min(down[i][k-1][j], down[i][k-1][j+(1<<(k-1))]);
}
}
for(int i=0; i<m; i++) {
for(int j=0; j+(1<<k)-1<n; j++) {
Left[i][k][j] = max(Left[i][k-1][j], Left[i][k-1][j+(1<<(k-1))]);
Right[i][k][j] = min(Right[i][k-1][j], Right[i][k-1][j+(1<<(k-1))]);
}
}
}
int ans = 0;
for(int len=1; len<=n-2; len++) {
for(int i=1; i+len-1<=n-2; i++) {
int sto[m];
for(int x=0; x<m; x++) sto[x] = -1;
for(int x=1; x+1<m; x++) {
int u, d, l, r;
bool alive;
u = i, d = i + len - 1;
// as left
l = x, r = right_query(x - 1, u, d) - 1;
sto[l] = r;
if(u <= d && l <= r && l > 0 && r + 1 < m) {
alive = 1;
alive &= (right_query(l - 1, u, d) > r);
alive &= (left_query(r + 1, u, d) < l);
alive &= (down_query(u - 1, l, r) > d);
alive &= (up_query(d + 1, l, r) < u);
ans += alive;
//if(alive) cout << "u = " << u << ", d = " << d << ", l = " << l << ", r = "<<r<<"\n";
}
// as right
l = left_query(x + 1, u, d) + 1, r = x;
if(u <= d && l <= r && sto[l] != r && l > 0 && r + 1 < m) {
alive = 1;
alive &= (right_query(l - 1, u, d) > r);
alive &= (left_query(r + 1, u, d) < l);
alive &= (down_query(u - 1, l, r) > d);
alive &= (up_query(d + 1, l, r) < u);
ans += alive;
//if(alive) cout << "u = " << u << ", d = " << d << ", l = " << l << ", r = "<<r<<"\n";
}
}
}
}
return ans;
}
/*
g++ -std=c++17 -O2 -o rect grader.cpp rect.cpp
./rect < input.txt
*/
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:107:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | if((d - u + 1) * (r - l + 1) == ll[i].size() && u > 0 && l > 0 && d + 1 < n && r + 1 < m) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
25076 KB |
Output is correct |
2 |
Correct |
11 ms |
37212 KB |
Output is correct |
3 |
Correct |
8 ms |
37212 KB |
Output is correct |
4 |
Correct |
6 ms |
37464 KB |
Output is correct |
5 |
Correct |
8 ms |
37212 KB |
Output is correct |
6 |
Correct |
8 ms |
37212 KB |
Output is correct |
7 |
Correct |
6 ms |
33116 KB |
Output is correct |
8 |
Correct |
5 ms |
31228 KB |
Output is correct |
9 |
Correct |
5 ms |
37212 KB |
Output is correct |
10 |
Correct |
5 ms |
37212 KB |
Output is correct |
11 |
Correct |
5 ms |
37208 KB |
Output is correct |
12 |
Correct |
7 ms |
37380 KB |
Output is correct |
13 |
Correct |
2 ms |
16732 KB |
Output is correct |
14 |
Correct |
3 ms |
22872 KB |
Output is correct |
15 |
Correct |
5 ms |
26972 KB |
Output is correct |
16 |
Correct |
4 ms |
22876 KB |
Output is correct |
17 |
Correct |
2 ms |
10588 KB |
Output is correct |
18 |
Correct |
2 ms |
10588 KB |
Output is correct |
19 |
Correct |
3 ms |
14684 KB |
Output is correct |
20 |
Correct |
2 ms |
14680 KB |
Output is correct |
21 |
Correct |
5 ms |
22872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
25076 KB |
Output is correct |
2 |
Correct |
11 ms |
37212 KB |
Output is correct |
3 |
Correct |
8 ms |
37212 KB |
Output is correct |
4 |
Correct |
6 ms |
37464 KB |
Output is correct |
5 |
Correct |
8 ms |
37212 KB |
Output is correct |
6 |
Correct |
8 ms |
37212 KB |
Output is correct |
7 |
Correct |
6 ms |
33116 KB |
Output is correct |
8 |
Correct |
5 ms |
31228 KB |
Output is correct |
9 |
Correct |
5 ms |
37212 KB |
Output is correct |
10 |
Correct |
5 ms |
37212 KB |
Output is correct |
11 |
Correct |
5 ms |
37208 KB |
Output is correct |
12 |
Correct |
7 ms |
37380 KB |
Output is correct |
13 |
Correct |
2 ms |
16732 KB |
Output is correct |
14 |
Correct |
3 ms |
22872 KB |
Output is correct |
15 |
Correct |
5 ms |
26972 KB |
Output is correct |
16 |
Correct |
4 ms |
22876 KB |
Output is correct |
17 |
Correct |
2 ms |
10588 KB |
Output is correct |
18 |
Correct |
2 ms |
10588 KB |
Output is correct |
19 |
Correct |
3 ms |
14684 KB |
Output is correct |
20 |
Correct |
2 ms |
14680 KB |
Output is correct |
21 |
Correct |
5 ms |
22872 KB |
Output is correct |
22 |
Correct |
16 ms |
52824 KB |
Output is correct |
23 |
Correct |
14 ms |
52764 KB |
Output is correct |
24 |
Correct |
13 ms |
49756 KB |
Output is correct |
25 |
Correct |
11 ms |
49752 KB |
Output is correct |
26 |
Correct |
11 ms |
46232 KB |
Output is correct |
27 |
Correct |
11 ms |
48220 KB |
Output is correct |
28 |
Correct |
11 ms |
48220 KB |
Output is correct |
29 |
Correct |
9 ms |
45660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
25076 KB |
Output is correct |
2 |
Correct |
11 ms |
37212 KB |
Output is correct |
3 |
Correct |
8 ms |
37212 KB |
Output is correct |
4 |
Correct |
6 ms |
37464 KB |
Output is correct |
5 |
Correct |
8 ms |
37212 KB |
Output is correct |
6 |
Correct |
8 ms |
37212 KB |
Output is correct |
7 |
Correct |
6 ms |
33116 KB |
Output is correct |
8 |
Correct |
5 ms |
31228 KB |
Output is correct |
9 |
Correct |
5 ms |
37212 KB |
Output is correct |
10 |
Correct |
5 ms |
37212 KB |
Output is correct |
11 |
Correct |
5 ms |
37208 KB |
Output is correct |
12 |
Correct |
7 ms |
37380 KB |
Output is correct |
13 |
Correct |
2 ms |
16732 KB |
Output is correct |
14 |
Correct |
3 ms |
22872 KB |
Output is correct |
15 |
Correct |
5 ms |
26972 KB |
Output is correct |
16 |
Correct |
4 ms |
22876 KB |
Output is correct |
17 |
Correct |
16 ms |
52824 KB |
Output is correct |
18 |
Correct |
14 ms |
52764 KB |
Output is correct |
19 |
Correct |
13 ms |
49756 KB |
Output is correct |
20 |
Correct |
11 ms |
49752 KB |
Output is correct |
21 |
Correct |
11 ms |
46232 KB |
Output is correct |
22 |
Correct |
11 ms |
48220 KB |
Output is correct |
23 |
Correct |
11 ms |
48220 KB |
Output is correct |
24 |
Correct |
9 ms |
45660 KB |
Output is correct |
25 |
Correct |
2 ms |
10588 KB |
Output is correct |
26 |
Correct |
2 ms |
10588 KB |
Output is correct |
27 |
Correct |
3 ms |
14684 KB |
Output is correct |
28 |
Correct |
2 ms |
14680 KB |
Output is correct |
29 |
Correct |
5 ms |
22872 KB |
Output is correct |
30 |
Correct |
70 ms |
65884 KB |
Output is correct |
31 |
Correct |
72 ms |
65880 KB |
Output is correct |
32 |
Correct |
70 ms |
65884 KB |
Output is correct |
33 |
Correct |
30 ms |
66136 KB |
Output is correct |
34 |
Correct |
35 ms |
65876 KB |
Output is correct |
35 |
Correct |
42 ms |
66132 KB |
Output is correct |
36 |
Correct |
38 ms |
65824 KB |
Output is correct |
37 |
Correct |
42 ms |
65628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
25076 KB |
Output is correct |
2 |
Correct |
11 ms |
37212 KB |
Output is correct |
3 |
Correct |
8 ms |
37212 KB |
Output is correct |
4 |
Correct |
6 ms |
37464 KB |
Output is correct |
5 |
Correct |
8 ms |
37212 KB |
Output is correct |
6 |
Correct |
8 ms |
37212 KB |
Output is correct |
7 |
Correct |
6 ms |
33116 KB |
Output is correct |
8 |
Correct |
5 ms |
31228 KB |
Output is correct |
9 |
Correct |
5 ms |
37212 KB |
Output is correct |
10 |
Correct |
5 ms |
37212 KB |
Output is correct |
11 |
Correct |
5 ms |
37208 KB |
Output is correct |
12 |
Correct |
7 ms |
37380 KB |
Output is correct |
13 |
Correct |
2 ms |
16732 KB |
Output is correct |
14 |
Correct |
3 ms |
22872 KB |
Output is correct |
15 |
Correct |
5 ms |
26972 KB |
Output is correct |
16 |
Correct |
4 ms |
22876 KB |
Output is correct |
17 |
Correct |
16 ms |
52824 KB |
Output is correct |
18 |
Correct |
14 ms |
52764 KB |
Output is correct |
19 |
Correct |
13 ms |
49756 KB |
Output is correct |
20 |
Correct |
11 ms |
49752 KB |
Output is correct |
21 |
Correct |
11 ms |
46232 KB |
Output is correct |
22 |
Correct |
11 ms |
48220 KB |
Output is correct |
23 |
Correct |
11 ms |
48220 KB |
Output is correct |
24 |
Correct |
9 ms |
45660 KB |
Output is correct |
25 |
Correct |
70 ms |
65884 KB |
Output is correct |
26 |
Correct |
72 ms |
65880 KB |
Output is correct |
27 |
Correct |
70 ms |
65884 KB |
Output is correct |
28 |
Correct |
30 ms |
66136 KB |
Output is correct |
29 |
Correct |
35 ms |
65876 KB |
Output is correct |
30 |
Correct |
42 ms |
66132 KB |
Output is correct |
31 |
Correct |
38 ms |
65824 KB |
Output is correct |
32 |
Correct |
42 ms |
65628 KB |
Output is correct |
33 |
Correct |
2 ms |
10588 KB |
Output is correct |
34 |
Correct |
2 ms |
10588 KB |
Output is correct |
35 |
Correct |
3 ms |
14684 KB |
Output is correct |
36 |
Correct |
2 ms |
14680 KB |
Output is correct |
37 |
Correct |
5 ms |
22872 KB |
Output is correct |
38 |
Correct |
2011 ms |
225480 KB |
Output is correct |
39 |
Correct |
1963 ms |
225488 KB |
Output is correct |
40 |
Correct |
1999 ms |
223664 KB |
Output is correct |
41 |
Correct |
1870 ms |
225620 KB |
Output is correct |
42 |
Correct |
3373 ms |
223640 KB |
Output is correct |
43 |
Correct |
3471 ms |
225268 KB |
Output is correct |
44 |
Correct |
3381 ms |
225484 KB |
Output is correct |
45 |
Correct |
2745 ms |
215556 KB |
Output is correct |
46 |
Correct |
74 ms |
66388 KB |
Output is correct |
47 |
Correct |
1000 ms |
221896 KB |
Output is correct |
48 |
Correct |
971 ms |
220272 KB |
Output is correct |
49 |
Correct |
1089 ms |
221900 KB |
Output is correct |
50 |
Correct |
380 ms |
148052 KB |
Output is correct |
51 |
Correct |
286 ms |
144608 KB |
Output is correct |
52 |
Correct |
1165 ms |
218756 KB |
Output is correct |
53 |
Correct |
1093 ms |
218704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
75344 KB |
Output is correct |
2 |
Correct |
24 ms |
71260 KB |
Output is correct |
3 |
Correct |
28 ms |
75588 KB |
Output is correct |
4 |
Correct |
4 ms |
20828 KB |
Output is correct |
5 |
Correct |
25 ms |
75356 KB |
Output is correct |
6 |
Correct |
27 ms |
79192 KB |
Output is correct |
7 |
Correct |
29 ms |
79304 KB |
Output is correct |
8 |
Correct |
27 ms |
79188 KB |
Output is correct |
9 |
Correct |
27 ms |
79196 KB |
Output is correct |
10 |
Correct |
18 ms |
59740 KB |
Output is correct |
11 |
Correct |
24 ms |
78876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10588 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
3 ms |
14684 KB |
Output is correct |
4 |
Correct |
2 ms |
14680 KB |
Output is correct |
5 |
Correct |
5 ms |
22872 KB |
Output is correct |
6 |
Correct |
3 ms |
12632 KB |
Output is correct |
7 |
Correct |
392 ms |
220660 KB |
Output is correct |
8 |
Correct |
975 ms |
468800 KB |
Output is correct |
9 |
Correct |
913 ms |
470160 KB |
Output is correct |
10 |
Correct |
918 ms |
471048 KB |
Output is correct |
11 |
Correct |
246 ms |
205888 KB |
Output is correct |
12 |
Correct |
544 ms |
394224 KB |
Output is correct |
13 |
Correct |
572 ms |
402156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
25076 KB |
Output is correct |
2 |
Correct |
11 ms |
37212 KB |
Output is correct |
3 |
Correct |
8 ms |
37212 KB |
Output is correct |
4 |
Correct |
6 ms |
37464 KB |
Output is correct |
5 |
Correct |
8 ms |
37212 KB |
Output is correct |
6 |
Correct |
8 ms |
37212 KB |
Output is correct |
7 |
Correct |
6 ms |
33116 KB |
Output is correct |
8 |
Correct |
5 ms |
31228 KB |
Output is correct |
9 |
Correct |
5 ms |
37212 KB |
Output is correct |
10 |
Correct |
5 ms |
37212 KB |
Output is correct |
11 |
Correct |
5 ms |
37208 KB |
Output is correct |
12 |
Correct |
7 ms |
37380 KB |
Output is correct |
13 |
Correct |
2 ms |
16732 KB |
Output is correct |
14 |
Correct |
3 ms |
22872 KB |
Output is correct |
15 |
Correct |
5 ms |
26972 KB |
Output is correct |
16 |
Correct |
4 ms |
22876 KB |
Output is correct |
17 |
Correct |
16 ms |
52824 KB |
Output is correct |
18 |
Correct |
14 ms |
52764 KB |
Output is correct |
19 |
Correct |
13 ms |
49756 KB |
Output is correct |
20 |
Correct |
11 ms |
49752 KB |
Output is correct |
21 |
Correct |
11 ms |
46232 KB |
Output is correct |
22 |
Correct |
11 ms |
48220 KB |
Output is correct |
23 |
Correct |
11 ms |
48220 KB |
Output is correct |
24 |
Correct |
9 ms |
45660 KB |
Output is correct |
25 |
Correct |
70 ms |
65884 KB |
Output is correct |
26 |
Correct |
72 ms |
65880 KB |
Output is correct |
27 |
Correct |
70 ms |
65884 KB |
Output is correct |
28 |
Correct |
30 ms |
66136 KB |
Output is correct |
29 |
Correct |
35 ms |
65876 KB |
Output is correct |
30 |
Correct |
42 ms |
66132 KB |
Output is correct |
31 |
Correct |
38 ms |
65824 KB |
Output is correct |
32 |
Correct |
42 ms |
65628 KB |
Output is correct |
33 |
Correct |
2011 ms |
225480 KB |
Output is correct |
34 |
Correct |
1963 ms |
225488 KB |
Output is correct |
35 |
Correct |
1999 ms |
223664 KB |
Output is correct |
36 |
Correct |
1870 ms |
225620 KB |
Output is correct |
37 |
Correct |
3373 ms |
223640 KB |
Output is correct |
38 |
Correct |
3471 ms |
225268 KB |
Output is correct |
39 |
Correct |
3381 ms |
225484 KB |
Output is correct |
40 |
Correct |
2745 ms |
215556 KB |
Output is correct |
41 |
Correct |
74 ms |
66388 KB |
Output is correct |
42 |
Correct |
1000 ms |
221896 KB |
Output is correct |
43 |
Correct |
971 ms |
220272 KB |
Output is correct |
44 |
Correct |
1089 ms |
221900 KB |
Output is correct |
45 |
Correct |
380 ms |
148052 KB |
Output is correct |
46 |
Correct |
286 ms |
144608 KB |
Output is correct |
47 |
Correct |
1165 ms |
218756 KB |
Output is correct |
48 |
Correct |
1093 ms |
218704 KB |
Output is correct |
49 |
Correct |
29 ms |
75344 KB |
Output is correct |
50 |
Correct |
24 ms |
71260 KB |
Output is correct |
51 |
Correct |
28 ms |
75588 KB |
Output is correct |
52 |
Correct |
4 ms |
20828 KB |
Output is correct |
53 |
Correct |
25 ms |
75356 KB |
Output is correct |
54 |
Correct |
27 ms |
79192 KB |
Output is correct |
55 |
Correct |
29 ms |
79304 KB |
Output is correct |
56 |
Correct |
27 ms |
79188 KB |
Output is correct |
57 |
Correct |
27 ms |
79196 KB |
Output is correct |
58 |
Correct |
18 ms |
59740 KB |
Output is correct |
59 |
Correct |
24 ms |
78876 KB |
Output is correct |
60 |
Correct |
3 ms |
12632 KB |
Output is correct |
61 |
Correct |
392 ms |
220660 KB |
Output is correct |
62 |
Correct |
975 ms |
468800 KB |
Output is correct |
63 |
Correct |
913 ms |
470160 KB |
Output is correct |
64 |
Correct |
918 ms |
471048 KB |
Output is correct |
65 |
Correct |
246 ms |
205888 KB |
Output is correct |
66 |
Correct |
544 ms |
394224 KB |
Output is correct |
67 |
Correct |
572 ms |
402156 KB |
Output is correct |
68 |
Correct |
2 ms |
10588 KB |
Output is correct |
69 |
Correct |
2 ms |
10588 KB |
Output is correct |
70 |
Correct |
3 ms |
14684 KB |
Output is correct |
71 |
Correct |
2 ms |
14680 KB |
Output is correct |
72 |
Correct |
5 ms |
22872 KB |
Output is correct |
73 |
Execution timed out |
5011 ms |
148396 KB |
Time limit exceeded |
74 |
Halted |
0 ms |
0 KB |
- |