#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include "rect.h"
using namespace std;
static int a[2505][2505], d[4][2505][2505], c[2505], df[4][2505][2505], lst[2505][2505];
static int n, m, nr;
struct str{
int a, b, c, d;
};
vector<str> w;
int cmp(str x, str y){
if(x.a != y.a){
return x.a < y.a;
}
if(x.b != y.b){
return x.b < y.b;
}
if(x.c != y.c){
return x.c < y.c;
}
return x.d < y.d;
}
static void verif(int i, int j, int ii, int jj){
if(i > ii){
swap(i, ii);
}
if(j > jj){
swap(j, jj);
}
if(i == 0 || j == 0 || i >= ii - 1 || j >= jj - 1 || ii == n + 1 || jj == m + 1){
return;
}
if( (d[0][ii - 1][jj] == j && df[0][ii - 1][jj] <= i + 1) || (d[1][ii - 1][j] == jj && df[1][ii - 1][j] <= i + 1) ){
if( (d[2][ii][jj - 1] == i && df[2][ii][jj - 1] <= j + 1) || (d[3][i][jj - 1] == ii && df[3][i][jj - 1] <= j + 1) ){
w.push_back( {i, j, ii, jj} );
}
}
}
long long count_rectangles(std::vector<std::vector<int> > a1) {
int i, j, ii, jj, u, x;
long long sol = 0;
n = a1.size();
m = a1[0].size();
for(i = 1; i <= n; i++){
for(j = 1; j <= m; j++){
a[i][j] = a1[i - 1][j - 1];
}
}
for(i = 1; i <= n; i++){
u = 0;
c[0] = 0;
for(j = 1; j <= m; j++){
while(u > 0 && a[i][ c[u] ] < a[i][j]){
u--;
}
d[0][i][j] = c[u];
c[++u] = j;
}
u = 0;
c[0] = m + 1;
for(j = m; j >= 1; j--){
while(u > 0 && a[i][ c[u] ] < a[i][j]){
u--;
}
d[1][i][j] = c[u];
c[++u] = j;
}
}
for(j = 1; j <= m; j++){
u = 0;
c[0] = 0;
for(i = 1; i <= n; i++){
while(u > 0 && a[ c[u] ][j] < a[i][j]){
u--;
}
d[2][i][j] = c[u];
c[++u] = i;
}
u = 0;
c[0] = n + 1;
for(i = n; i >= 1; i--){
while(u > 0 && a[ c[u] ][j] < a[i][j]){
u--;
}
d[3][i][j] = c[u];
c[++u] = i;
}
}
for(i = 1; i <= n; i++){
for(ii = 0; ii < 2; ii++){
for(j = 1; j <= m; j++){
df[ii][i][j] = i;
if(d[ii][i - 1][j] == d[ii][i][j]){
df[ii][i][j] = df[ii][i - 1][j];
}
else if(d[1 - ii][i - 1][ d[ii][i][j] ] == j){
df[ii][i][j] = df[1 - ii][i - 1][ d[ii][i][j] ];
}
}
}
}
for(j = 1; j <= m; j++){
for(ii = 2; ii < 4; ii++){
for(i = 1; i <= n; i++){
df[ii][i][j] = j;
if(d[ii][i][j - 1] == d[ii][i][j]){
df[ii][i][j] = df[ii][i][j - 1];
}
else if(d[5 - ii][ d[ii][i][j] ][j - 1] == i){
df[ii][i][j] = df[5 - ii][ d[ii][i][j] ][j - 1];
}
}
}
}
for(i = 2; i < n; i++){
for(j = 2; j < m; j++){
verif(i + 1, j + 1, d[2][i + 1][j], d[0][i][j + 1]);
verif(i + 1, j - 1, d[2][i + 1][j], d[1][i][j - 1]);
x = d[3][i - 1][j];
verif(i - 1, j - 1, x, d[1][i][j - 1]);
verif(i - 1, j + 1, x, d[0][i][j + 1]);
verif(i - 1, j - 1, x, d[1][x - 1][j - 1]);
verif(i - 1, j + 1, x, d[0][x - 1][j + 1]);
}
}
sort(w.begin(), w.end(), cmp);
if(w.size() == 0){
return 0;
}
sol = 1;
for(i = 1; i < w.size(); i++){
if(w[i].a != w[sol - 1].a || w[i].b != w[sol - 1].b || w[i].c != w[sol - 1].c || w[i].d != w[sol - 1].d ){
w[++sol - 1] = w[i];
}
}
return sol;
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:137:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<str>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(i = 1; i < w.size(); i++){
| ~~^~~~~~~~~~
rect.cpp:43:16: warning: unused variable 'jj' [-Wunused-variable]
43 | int i, j, ii, jj, u, x;
| ^~
rect.cpp: At global scope:
rect.cpp:8:18: warning: 'nr' defined but not used [-Wunused-variable]
8 | static int n, m, nr;
| ^~
rect.cpp:7:73: warning: 'lst' defined but not used [-Wunused-variable]
7 | static int a[2505][2505], d[4][2505][2505], c[2505], df[4][2505][2505], lst[2505][2505];
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
1512 KB |
Output is correct |
3 |
Correct |
2 ms |
1536 KB |
Output is correct |
4 |
Correct |
1 ms |
1536 KB |
Output is correct |
5 |
Correct |
1 ms |
1408 KB |
Output is correct |
6 |
Correct |
1 ms |
1536 KB |
Output is correct |
7 |
Correct |
1 ms |
1408 KB |
Output is correct |
8 |
Correct |
1 ms |
768 KB |
Output is correct |
9 |
Correct |
1 ms |
1536 KB |
Output is correct |
10 |
Correct |
1 ms |
1440 KB |
Output is correct |
11 |
Correct |
1 ms |
1536 KB |
Output is correct |
12 |
Correct |
1 ms |
1536 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
672 KB |
Output is correct |
15 |
Correct |
1 ms |
768 KB |
Output is correct |
16 |
Correct |
1 ms |
512 KB |
Output is correct |
17 |
Correct |
1 ms |
384 KB |
Output is correct |
18 |
Correct |
1 ms |
384 KB |
Output is correct |
19 |
Correct |
1 ms |
1536 KB |
Output is correct |
20 |
Correct |
1 ms |
1408 KB |
Output is correct |
21 |
Correct |
1 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
1512 KB |
Output is correct |
3 |
Correct |
2 ms |
1536 KB |
Output is correct |
4 |
Correct |
1 ms |
1536 KB |
Output is correct |
5 |
Correct |
1 ms |
1408 KB |
Output is correct |
6 |
Correct |
1 ms |
1536 KB |
Output is correct |
7 |
Correct |
1 ms |
1408 KB |
Output is correct |
8 |
Correct |
1 ms |
768 KB |
Output is correct |
9 |
Correct |
1 ms |
1536 KB |
Output is correct |
10 |
Correct |
1 ms |
1440 KB |
Output is correct |
11 |
Correct |
1 ms |
1536 KB |
Output is correct |
12 |
Correct |
1 ms |
1536 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
672 KB |
Output is correct |
15 |
Correct |
1 ms |
768 KB |
Output is correct |
16 |
Correct |
1 ms |
512 KB |
Output is correct |
17 |
Correct |
4 ms |
3968 KB |
Output is correct |
18 |
Correct |
5 ms |
3968 KB |
Output is correct |
19 |
Correct |
4 ms |
3968 KB |
Output is correct |
20 |
Correct |
4 ms |
3712 KB |
Output is correct |
21 |
Correct |
4 ms |
3712 KB |
Output is correct |
22 |
Correct |
4 ms |
3712 KB |
Output is correct |
23 |
Correct |
4 ms |
3712 KB |
Output is correct |
24 |
Correct |
3 ms |
3456 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
1 ms |
384 KB |
Output is correct |
27 |
Correct |
1 ms |
1536 KB |
Output is correct |
28 |
Correct |
1 ms |
1408 KB |
Output is correct |
29 |
Correct |
1 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
1512 KB |
Output is correct |
3 |
Correct |
2 ms |
1536 KB |
Output is correct |
4 |
Correct |
1 ms |
1536 KB |
Output is correct |
5 |
Correct |
1 ms |
1408 KB |
Output is correct |
6 |
Correct |
1 ms |
1536 KB |
Output is correct |
7 |
Correct |
1 ms |
1408 KB |
Output is correct |
8 |
Correct |
1 ms |
768 KB |
Output is correct |
9 |
Correct |
1 ms |
1536 KB |
Output is correct |
10 |
Correct |
1 ms |
1440 KB |
Output is correct |
11 |
Correct |
1 ms |
1536 KB |
Output is correct |
12 |
Correct |
1 ms |
1536 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
672 KB |
Output is correct |
15 |
Correct |
1 ms |
768 KB |
Output is correct |
16 |
Correct |
1 ms |
512 KB |
Output is correct |
17 |
Correct |
4 ms |
3968 KB |
Output is correct |
18 |
Correct |
5 ms |
3968 KB |
Output is correct |
19 |
Correct |
4 ms |
3968 KB |
Output is correct |
20 |
Correct |
4 ms |
3712 KB |
Output is correct |
21 |
Correct |
4 ms |
3712 KB |
Output is correct |
22 |
Correct |
4 ms |
3712 KB |
Output is correct |
23 |
Correct |
4 ms |
3712 KB |
Output is correct |
24 |
Correct |
3 ms |
3456 KB |
Output is correct |
25 |
Correct |
20 ms |
11768 KB |
Output is correct |
26 |
Correct |
20 ms |
11896 KB |
Output is correct |
27 |
Correct |
18 ms |
11768 KB |
Output is correct |
28 |
Correct |
14 ms |
9856 KB |
Output is correct |
29 |
Correct |
14 ms |
10112 KB |
Output is correct |
30 |
Correct |
15 ms |
10240 KB |
Output is correct |
31 |
Correct |
15 ms |
10240 KB |
Output is correct |
32 |
Correct |
15 ms |
10168 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
1536 KB |
Output is correct |
36 |
Correct |
1 ms |
1408 KB |
Output is correct |
37 |
Correct |
1 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
1512 KB |
Output is correct |
3 |
Correct |
2 ms |
1536 KB |
Output is correct |
4 |
Correct |
1 ms |
1536 KB |
Output is correct |
5 |
Correct |
1 ms |
1408 KB |
Output is correct |
6 |
Correct |
1 ms |
1536 KB |
Output is correct |
7 |
Correct |
1 ms |
1408 KB |
Output is correct |
8 |
Correct |
1 ms |
768 KB |
Output is correct |
9 |
Correct |
1 ms |
1536 KB |
Output is correct |
10 |
Correct |
1 ms |
1440 KB |
Output is correct |
11 |
Correct |
1 ms |
1536 KB |
Output is correct |
12 |
Correct |
1 ms |
1536 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
672 KB |
Output is correct |
15 |
Correct |
1 ms |
768 KB |
Output is correct |
16 |
Correct |
1 ms |
512 KB |
Output is correct |
17 |
Correct |
4 ms |
3968 KB |
Output is correct |
18 |
Correct |
5 ms |
3968 KB |
Output is correct |
19 |
Correct |
4 ms |
3968 KB |
Output is correct |
20 |
Correct |
4 ms |
3712 KB |
Output is correct |
21 |
Correct |
4 ms |
3712 KB |
Output is correct |
22 |
Correct |
4 ms |
3712 KB |
Output is correct |
23 |
Correct |
4 ms |
3712 KB |
Output is correct |
24 |
Correct |
3 ms |
3456 KB |
Output is correct |
25 |
Correct |
20 ms |
11768 KB |
Output is correct |
26 |
Correct |
20 ms |
11896 KB |
Output is correct |
27 |
Correct |
18 ms |
11768 KB |
Output is correct |
28 |
Correct |
14 ms |
9856 KB |
Output is correct |
29 |
Correct |
14 ms |
10112 KB |
Output is correct |
30 |
Correct |
15 ms |
10240 KB |
Output is correct |
31 |
Correct |
15 ms |
10240 KB |
Output is correct |
32 |
Correct |
15 ms |
10168 KB |
Output is correct |
33 |
Correct |
115 ms |
49916 KB |
Output is correct |
34 |
Correct |
103 ms |
49912 KB |
Output is correct |
35 |
Correct |
102 ms |
49912 KB |
Output is correct |
36 |
Correct |
95 ms |
49968 KB |
Output is correct |
37 |
Correct |
239 ms |
66656 KB |
Output is correct |
38 |
Correct |
244 ms |
66656 KB |
Output is correct |
39 |
Correct |
233 ms |
66916 KB |
Output is correct |
40 |
Correct |
232 ms |
63716 KB |
Output is correct |
41 |
Correct |
121 ms |
49900 KB |
Output is correct |
42 |
Correct |
135 ms |
51944 KB |
Output is correct |
43 |
Correct |
169 ms |
52840 KB |
Output is correct |
44 |
Correct |
170 ms |
54688 KB |
Output is correct |
45 |
Correct |
89 ms |
40304 KB |
Output is correct |
46 |
Correct |
78 ms |
27632 KB |
Output is correct |
47 |
Correct |
169 ms |
53780 KB |
Output is correct |
48 |
Correct |
167 ms |
54756 KB |
Output is correct |
49 |
Correct |
1 ms |
384 KB |
Output is correct |
50 |
Correct |
1 ms |
384 KB |
Output is correct |
51 |
Correct |
1 ms |
1536 KB |
Output is correct |
52 |
Correct |
1 ms |
1408 KB |
Output is correct |
53 |
Correct |
1 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
852 KB |
Output is correct |
2 |
Correct |
2 ms |
896 KB |
Output is correct |
3 |
Correct |
1 ms |
768 KB |
Output is correct |
4 |
Correct |
1 ms |
512 KB |
Output is correct |
5 |
Correct |
2 ms |
768 KB |
Output is correct |
6 |
Correct |
2 ms |
768 KB |
Output is correct |
7 |
Correct |
2 ms |
768 KB |
Output is correct |
8 |
Correct |
1 ms |
768 KB |
Output is correct |
9 |
Correct |
2 ms |
768 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
764 KB |
Output is correct |
2 |
Correct |
670 ms |
152732 KB |
Output is correct |
3 |
Correct |
1556 ms |
302780 KB |
Output is correct |
4 |
Correct |
1467 ms |
304780 KB |
Output is correct |
5 |
Correct |
1496 ms |
303740 KB |
Output is correct |
6 |
Correct |
468 ms |
134392 KB |
Output is correct |
7 |
Correct |
962 ms |
267640 KB |
Output is correct |
8 |
Correct |
982 ms |
270200 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
1536 KB |
Output is correct |
12 |
Correct |
1 ms |
1408 KB |
Output is correct |
13 |
Correct |
1 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
1512 KB |
Output is correct |
3 |
Correct |
2 ms |
1536 KB |
Output is correct |
4 |
Correct |
1 ms |
1536 KB |
Output is correct |
5 |
Correct |
1 ms |
1408 KB |
Output is correct |
6 |
Correct |
1 ms |
1536 KB |
Output is correct |
7 |
Correct |
1 ms |
1408 KB |
Output is correct |
8 |
Correct |
1 ms |
768 KB |
Output is correct |
9 |
Correct |
1 ms |
1536 KB |
Output is correct |
10 |
Correct |
1 ms |
1440 KB |
Output is correct |
11 |
Correct |
1 ms |
1536 KB |
Output is correct |
12 |
Correct |
1 ms |
1536 KB |
Output is correct |
13 |
Correct |
0 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
672 KB |
Output is correct |
15 |
Correct |
1 ms |
768 KB |
Output is correct |
16 |
Correct |
1 ms |
512 KB |
Output is correct |
17 |
Correct |
4 ms |
3968 KB |
Output is correct |
18 |
Correct |
5 ms |
3968 KB |
Output is correct |
19 |
Correct |
4 ms |
3968 KB |
Output is correct |
20 |
Correct |
4 ms |
3712 KB |
Output is correct |
21 |
Correct |
4 ms |
3712 KB |
Output is correct |
22 |
Correct |
4 ms |
3712 KB |
Output is correct |
23 |
Correct |
4 ms |
3712 KB |
Output is correct |
24 |
Correct |
3 ms |
3456 KB |
Output is correct |
25 |
Correct |
20 ms |
11768 KB |
Output is correct |
26 |
Correct |
20 ms |
11896 KB |
Output is correct |
27 |
Correct |
18 ms |
11768 KB |
Output is correct |
28 |
Correct |
14 ms |
9856 KB |
Output is correct |
29 |
Correct |
14 ms |
10112 KB |
Output is correct |
30 |
Correct |
15 ms |
10240 KB |
Output is correct |
31 |
Correct |
15 ms |
10240 KB |
Output is correct |
32 |
Correct |
15 ms |
10168 KB |
Output is correct |
33 |
Correct |
115 ms |
49916 KB |
Output is correct |
34 |
Correct |
103 ms |
49912 KB |
Output is correct |
35 |
Correct |
102 ms |
49912 KB |
Output is correct |
36 |
Correct |
95 ms |
49968 KB |
Output is correct |
37 |
Correct |
239 ms |
66656 KB |
Output is correct |
38 |
Correct |
244 ms |
66656 KB |
Output is correct |
39 |
Correct |
233 ms |
66916 KB |
Output is correct |
40 |
Correct |
232 ms |
63716 KB |
Output is correct |
41 |
Correct |
121 ms |
49900 KB |
Output is correct |
42 |
Correct |
135 ms |
51944 KB |
Output is correct |
43 |
Correct |
169 ms |
52840 KB |
Output is correct |
44 |
Correct |
170 ms |
54688 KB |
Output is correct |
45 |
Correct |
89 ms |
40304 KB |
Output is correct |
46 |
Correct |
78 ms |
27632 KB |
Output is correct |
47 |
Correct |
169 ms |
53780 KB |
Output is correct |
48 |
Correct |
167 ms |
54756 KB |
Output is correct |
49 |
Correct |
1 ms |
852 KB |
Output is correct |
50 |
Correct |
2 ms |
896 KB |
Output is correct |
51 |
Correct |
1 ms |
768 KB |
Output is correct |
52 |
Correct |
1 ms |
512 KB |
Output is correct |
53 |
Correct |
2 ms |
768 KB |
Output is correct |
54 |
Correct |
2 ms |
768 KB |
Output is correct |
55 |
Correct |
2 ms |
768 KB |
Output is correct |
56 |
Correct |
1 ms |
768 KB |
Output is correct |
57 |
Correct |
2 ms |
768 KB |
Output is correct |
58 |
Correct |
1 ms |
512 KB |
Output is correct |
59 |
Correct |
1 ms |
640 KB |
Output is correct |
60 |
Correct |
1 ms |
764 KB |
Output is correct |
61 |
Correct |
670 ms |
152732 KB |
Output is correct |
62 |
Correct |
1556 ms |
302780 KB |
Output is correct |
63 |
Correct |
1467 ms |
304780 KB |
Output is correct |
64 |
Correct |
1496 ms |
303740 KB |
Output is correct |
65 |
Correct |
468 ms |
134392 KB |
Output is correct |
66 |
Correct |
962 ms |
267640 KB |
Output is correct |
67 |
Correct |
982 ms |
270200 KB |
Output is correct |
68 |
Correct |
1239 ms |
270536 KB |
Output is correct |
69 |
Correct |
1231 ms |
280440 KB |
Output is correct |
70 |
Correct |
1097 ms |
280056 KB |
Output is correct |
71 |
Correct |
1111 ms |
280132 KB |
Output is correct |
72 |
Correct |
3496 ms |
542764 KB |
Output is correct |
73 |
Correct |
1214 ms |
204992 KB |
Output is correct |
74 |
Correct |
1386 ms |
289752 KB |
Output is correct |
75 |
Correct |
2066 ms |
340632 KB |
Output is correct |
76 |
Correct |
1446 ms |
200760 KB |
Output is correct |
77 |
Correct |
1942 ms |
333920 KB |
Output is correct |
78 |
Correct |
2373 ms |
345624 KB |
Output is correct |
79 |
Correct |
1277 ms |
199776 KB |
Output is correct |
80 |
Correct |
2176 ms |
345772 KB |
Output is correct |
81 |
Correct |
2341 ms |
338328 KB |
Output is correct |
82 |
Correct |
2095 ms |
387480 KB |
Output is correct |
83 |
Correct |
3448 ms |
542548 KB |
Output is correct |
84 |
Correct |
3456 ms |
542672 KB |
Output is correct |
85 |
Correct |
3413 ms |
542668 KB |
Output is correct |
86 |
Correct |
1 ms |
384 KB |
Output is correct |
87 |
Correct |
1 ms |
384 KB |
Output is correct |
88 |
Correct |
1 ms |
1536 KB |
Output is correct |
89 |
Correct |
1 ms |
1408 KB |
Output is correct |
90 |
Correct |
1 ms |
768 KB |
Output is correct |