# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
296672 |
2020-09-10T18:50:26 Z |
ChrisT |
Rectangles (IOI19_rect) |
C++17 |
|
2883 ms |
378964 KB |
#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
inline long long hsh (int a, int b, int c, int d) {
return ((long long)a << 36) | ((long long)b << 24) | ((long long)c << 12) | ((long long)d);
}
long long count_rectangles (vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
vector<vector<int>> nextLeft(n,vector<int>(m,1e9)), nextRight(n,vector<int>(m,-1)), nextUp(n,vector<int>(m,1e9)), nextDown(n,vector<int>(m,-1)), upFromLeft(n,vector<int>(m)),upFromRight(n,vector<int>(m)),leftFromDown(n,vector<int>(m)),leftFromUp(n,vector<int>(m));
for (int i = 0; i < n; i++) {
vector<int> stk;
for (int j = 0; j < m; j++) {
while (!stk.empty() && a[i][stk.back()] < a[i][j]) stk.pop_back();
if (!stk.empty()) {
nextLeft[i][j] = stk.back();
upFromLeft[i][j] = 1;
if (i > 0 && nextLeft[i-1][j] == nextLeft[i][j]) upFromLeft[i][j] += upFromLeft[i-1][j];
else if (i > 0 && nextRight[i-1][stk.back()] == j) upFromLeft[i][j] += upFromRight[i-1][stk.back()];
}
stk.push_back(j);
}
stk.clear();
for (int j = m-1; j >= 0; j--) {
while (!stk.empty() && a[i][stk.back()] < a[i][j]) stk.pop_back();
if (!stk.empty()) {
nextRight[i][j] = stk.back();
upFromRight[i][j] = 1;
if (i > 0 && nextRight[i-1][j] == nextRight[i][j]) upFromRight[i][j] += upFromRight[i-1][j];
else if (i > 0 && nextLeft[i-1][stk.back()] == j) upFromRight[i][j] += upFromLeft[i-1][stk.back()];
}
stk.push_back(j);
}
}
for (int j = 0; j < m; j++) {
vector<int> stk;
for (int i = 0; i < n; i++) {
while (!stk.empty() && a[stk.back()][j] < a[i][j]) stk.pop_back();
if (!stk.empty()) {
nextUp[i][j] = stk.back();
leftFromUp[i][j] = 1;
if (j > 0 && nextUp[i][j-1] == nextUp[i][j]) leftFromUp[i][j] += leftFromUp[i][j-1];
else if (j > 0 && nextDown[stk.back()][j-1] == i) leftFromUp[i][j] += leftFromDown[stk.back()][j-1];
}
stk.push_back(i);
}
stk.clear();
for (int i = n-1; i >= 0; i--) {
while (!stk.empty() && a[stk.back()][j] < a[i][j]) stk.pop_back();
if (!stk.empty()) {
nextDown[i][j] = stk.back();
leftFromDown[i][j] = 1;
if (j > 0 && nextDown[i][j-1] == nextDown[i][j]) leftFromDown[i][j] += leftFromDown[i][j-1];
else if (j > 0 && nextUp[stk.back()][j-1] == i) leftFromDown[i][j] += leftFromUp[stk.back()][j-1];
}
stk.push_back(i);
}
}
auto works = [&] (int bx, int ry, int tx, int ly) {
return ((nextLeft[bx-1][ry] == ly && bx - upFromLeft[bx-1][ry] <= tx + 1) || (nextRight[bx-1][ly] == ry && bx - upFromRight[bx-1][ly] <= tx + 1)) && ((nextUp[bx][ry-1] == tx && ry - leftFromUp[bx][ry-1] <= ly + 1) || (nextDown[tx][ry-1] == bx && ry - leftFromDown[tx][ry-1] <= ly + 1));
};
auto ok = [&] (int x) {return x >= 0 && x < n;};
vector<long long> can;
auto go = [&] (int i, int j, int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= m || abs(i-x) <= 1 || abs(j-y) <= 1) return;
if (x < i) swap(x,i);
if (y < j) swap(y,j);
if (works(x,y,i,j)) can.push_back(hsh(i,j,x,y));
};
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i > 0 && j > 0 && ok(nextUp[i][j-1])) go(i,j,nextUp[i][j-1],nextLeft[i-1][j]), go(i,j,nextUp[i][j-1],nextLeft[nextUp[i][j-1]+1][j]);
if (i > 0 && j+1 < m && ok(nextUp[i][j+1])) go(i,j,nextUp[i][j+1],nextRight[i-1][j]), go(i,j,nextUp[i][j+1],nextRight[nextUp[i][j+1]+1][j]);
if (i+1 < n && j > 0 && ok(nextDown[i][j-1])) go(i,j,nextDown[i][j-1],nextLeft[i+1][j]), go(i,j,nextDown[i][j-1],nextLeft[nextDown[i][j-1]-1][j]);
if (i+1 < n && j+1 < m && ok(nextDown[i][j+1])) go(i,j,nextDown[i][j+1],nextRight[i+1][j]), go(i,j,nextDown[i][j+1],nextRight[nextDown[i][j+1]-1][j]);
}
}
sort(can.begin(),can.end());
return unique(can.begin(),can.end()) - can.begin();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 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 |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
0 ms |
256 KB |
Output is correct |
18 |
Correct |
0 ms |
256 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
0 ms |
384 KB |
Output is correct |
21 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 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 |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
3 ms |
768 KB |
Output is correct |
18 |
Correct |
3 ms |
768 KB |
Output is correct |
19 |
Correct |
3 ms |
768 KB |
Output is correct |
20 |
Correct |
2 ms |
640 KB |
Output is correct |
21 |
Correct |
2 ms |
640 KB |
Output is correct |
22 |
Correct |
2 ms |
640 KB |
Output is correct |
23 |
Correct |
3 ms |
640 KB |
Output is correct |
24 |
Correct |
1 ms |
512 KB |
Output is correct |
25 |
Correct |
0 ms |
256 KB |
Output is correct |
26 |
Correct |
0 ms |
256 KB |
Output is correct |
27 |
Correct |
1 ms |
384 KB |
Output is correct |
28 |
Correct |
0 ms |
384 KB |
Output is correct |
29 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 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 |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
3 ms |
768 KB |
Output is correct |
18 |
Correct |
3 ms |
768 KB |
Output is correct |
19 |
Correct |
3 ms |
768 KB |
Output is correct |
20 |
Correct |
2 ms |
640 KB |
Output is correct |
21 |
Correct |
2 ms |
640 KB |
Output is correct |
22 |
Correct |
2 ms |
640 KB |
Output is correct |
23 |
Correct |
3 ms |
640 KB |
Output is correct |
24 |
Correct |
1 ms |
512 KB |
Output is correct |
25 |
Correct |
14 ms |
3064 KB |
Output is correct |
26 |
Correct |
15 ms |
3064 KB |
Output is correct |
27 |
Correct |
15 ms |
3064 KB |
Output is correct |
28 |
Correct |
10 ms |
2304 KB |
Output is correct |
29 |
Correct |
12 ms |
2304 KB |
Output is correct |
30 |
Correct |
16 ms |
2304 KB |
Output is correct |
31 |
Correct |
12 ms |
2304 KB |
Output is correct |
32 |
Correct |
14 ms |
2336 KB |
Output is correct |
33 |
Correct |
0 ms |
256 KB |
Output is correct |
34 |
Correct |
0 ms |
256 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
0 ms |
384 KB |
Output is correct |
37 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 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 |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
3 ms |
768 KB |
Output is correct |
18 |
Correct |
3 ms |
768 KB |
Output is correct |
19 |
Correct |
3 ms |
768 KB |
Output is correct |
20 |
Correct |
2 ms |
640 KB |
Output is correct |
21 |
Correct |
2 ms |
640 KB |
Output is correct |
22 |
Correct |
2 ms |
640 KB |
Output is correct |
23 |
Correct |
3 ms |
640 KB |
Output is correct |
24 |
Correct |
1 ms |
512 KB |
Output is correct |
25 |
Correct |
14 ms |
3064 KB |
Output is correct |
26 |
Correct |
15 ms |
3064 KB |
Output is correct |
27 |
Correct |
15 ms |
3064 KB |
Output is correct |
28 |
Correct |
10 ms |
2304 KB |
Output is correct |
29 |
Correct |
12 ms |
2304 KB |
Output is correct |
30 |
Correct |
16 ms |
2304 KB |
Output is correct |
31 |
Correct |
12 ms |
2304 KB |
Output is correct |
32 |
Correct |
14 ms |
2336 KB |
Output is correct |
33 |
Correct |
62 ms |
19832 KB |
Output is correct |
34 |
Correct |
64 ms |
19832 KB |
Output is correct |
35 |
Correct |
64 ms |
19832 KB |
Output is correct |
36 |
Correct |
65 ms |
19832 KB |
Output is correct |
37 |
Correct |
191 ms |
28132 KB |
Output is correct |
38 |
Correct |
188 ms |
28132 KB |
Output is correct |
39 |
Correct |
184 ms |
28132 KB |
Output is correct |
40 |
Correct |
177 ms |
26852 KB |
Output is correct |
41 |
Correct |
102 ms |
21992 KB |
Output is correct |
42 |
Correct |
120 ms |
21996 KB |
Output is correct |
43 |
Correct |
151 ms |
24036 KB |
Output is correct |
44 |
Correct |
164 ms |
24040 KB |
Output is correct |
45 |
Correct |
77 ms |
12268 KB |
Output is correct |
46 |
Correct |
80 ms |
12276 KB |
Output is correct |
47 |
Correct |
152 ms |
24040 KB |
Output is correct |
48 |
Correct |
152 ms |
24040 KB |
Output is correct |
49 |
Correct |
0 ms |
256 KB |
Output is correct |
50 |
Correct |
0 ms |
256 KB |
Output is correct |
51 |
Correct |
1 ms |
384 KB |
Output is correct |
52 |
Correct |
0 ms |
384 KB |
Output is correct |
53 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
768 KB |
Output is correct |
2 |
Correct |
2 ms |
640 KB |
Output is correct |
3 |
Correct |
1 ms |
640 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
640 KB |
Output is correct |
6 |
Correct |
2 ms |
640 KB |
Output is correct |
7 |
Correct |
2 ms |
640 KB |
Output is correct |
8 |
Correct |
2 ms |
640 KB |
Output is correct |
9 |
Correct |
2 ms |
640 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
699 ms |
121320 KB |
Output is correct |
3 |
Correct |
1545 ms |
261168 KB |
Output is correct |
4 |
Correct |
1557 ms |
265680 KB |
Output is correct |
5 |
Correct |
1563 ms |
265296 KB |
Output is correct |
6 |
Correct |
491 ms |
125304 KB |
Output is correct |
7 |
Correct |
946 ms |
233720 KB |
Output is correct |
8 |
Correct |
1014 ms |
248696 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
0 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 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 |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
3 ms |
768 KB |
Output is correct |
18 |
Correct |
3 ms |
768 KB |
Output is correct |
19 |
Correct |
3 ms |
768 KB |
Output is correct |
20 |
Correct |
2 ms |
640 KB |
Output is correct |
21 |
Correct |
2 ms |
640 KB |
Output is correct |
22 |
Correct |
2 ms |
640 KB |
Output is correct |
23 |
Correct |
3 ms |
640 KB |
Output is correct |
24 |
Correct |
1 ms |
512 KB |
Output is correct |
25 |
Correct |
14 ms |
3064 KB |
Output is correct |
26 |
Correct |
15 ms |
3064 KB |
Output is correct |
27 |
Correct |
15 ms |
3064 KB |
Output is correct |
28 |
Correct |
10 ms |
2304 KB |
Output is correct |
29 |
Correct |
12 ms |
2304 KB |
Output is correct |
30 |
Correct |
16 ms |
2304 KB |
Output is correct |
31 |
Correct |
12 ms |
2304 KB |
Output is correct |
32 |
Correct |
14 ms |
2336 KB |
Output is correct |
33 |
Correct |
62 ms |
19832 KB |
Output is correct |
34 |
Correct |
64 ms |
19832 KB |
Output is correct |
35 |
Correct |
64 ms |
19832 KB |
Output is correct |
36 |
Correct |
65 ms |
19832 KB |
Output is correct |
37 |
Correct |
191 ms |
28132 KB |
Output is correct |
38 |
Correct |
188 ms |
28132 KB |
Output is correct |
39 |
Correct |
184 ms |
28132 KB |
Output is correct |
40 |
Correct |
177 ms |
26852 KB |
Output is correct |
41 |
Correct |
102 ms |
21992 KB |
Output is correct |
42 |
Correct |
120 ms |
21996 KB |
Output is correct |
43 |
Correct |
151 ms |
24036 KB |
Output is correct |
44 |
Correct |
164 ms |
24040 KB |
Output is correct |
45 |
Correct |
77 ms |
12268 KB |
Output is correct |
46 |
Correct |
80 ms |
12276 KB |
Output is correct |
47 |
Correct |
152 ms |
24040 KB |
Output is correct |
48 |
Correct |
152 ms |
24040 KB |
Output is correct |
49 |
Correct |
2 ms |
768 KB |
Output is correct |
50 |
Correct |
2 ms |
640 KB |
Output is correct |
51 |
Correct |
1 ms |
640 KB |
Output is correct |
52 |
Correct |
0 ms |
256 KB |
Output is correct |
53 |
Correct |
2 ms |
640 KB |
Output is correct |
54 |
Correct |
2 ms |
640 KB |
Output is correct |
55 |
Correct |
2 ms |
640 KB |
Output is correct |
56 |
Correct |
2 ms |
640 KB |
Output is correct |
57 |
Correct |
2 ms |
640 KB |
Output is correct |
58 |
Correct |
1 ms |
384 KB |
Output is correct |
59 |
Correct |
1 ms |
512 KB |
Output is correct |
60 |
Correct |
0 ms |
256 KB |
Output is correct |
61 |
Correct |
699 ms |
121320 KB |
Output is correct |
62 |
Correct |
1545 ms |
261168 KB |
Output is correct |
63 |
Correct |
1557 ms |
265680 KB |
Output is correct |
64 |
Correct |
1563 ms |
265296 KB |
Output is correct |
65 |
Correct |
491 ms |
125304 KB |
Output is correct |
66 |
Correct |
946 ms |
233720 KB |
Output is correct |
67 |
Correct |
1014 ms |
248696 KB |
Output is correct |
68 |
Correct |
1230 ms |
249720 KB |
Output is correct |
69 |
Correct |
1153 ms |
249864 KB |
Output is correct |
70 |
Correct |
1099 ms |
249208 KB |
Output is correct |
71 |
Correct |
1100 ms |
247928 KB |
Output is correct |
72 |
Correct |
2837 ms |
378964 KB |
Output is correct |
73 |
Correct |
1418 ms |
183100 KB |
Output is correct |
74 |
Correct |
1421 ms |
191556 KB |
Output is correct |
75 |
Correct |
2347 ms |
312040 KB |
Output is correct |
76 |
Correct |
1498 ms |
183872 KB |
Output is correct |
77 |
Correct |
1876 ms |
232516 KB |
Output is correct |
78 |
Correct |
2432 ms |
312008 KB |
Output is correct |
79 |
Correct |
1320 ms |
180696 KB |
Output is correct |
80 |
Correct |
2272 ms |
312120 KB |
Output is correct |
81 |
Correct |
2216 ms |
274780 KB |
Output is correct |
82 |
Correct |
1676 ms |
216984 KB |
Output is correct |
83 |
Correct |
2883 ms |
377620 KB |
Output is correct |
84 |
Correct |
2852 ms |
377780 KB |
Output is correct |
85 |
Correct |
2869 ms |
377812 KB |
Output is correct |
86 |
Correct |
0 ms |
256 KB |
Output is correct |
87 |
Correct |
0 ms |
256 KB |
Output is correct |
88 |
Correct |
1 ms |
384 KB |
Output is correct |
89 |
Correct |
0 ms |
384 KB |
Output is correct |
90 |
Correct |
0 ms |
256 KB |
Output is correct |