#include "rect.h"
#include<bits/stdc++.h>
using namespace std;int maxst[2502][2502], maxdr[2502][2502], maxup[2502][2502], maxdwn[2502][2502];
int upleft[2502][2502], downleft[2502][2502], leftup[2502][2502], rightup[2502][2502];
vector<long long> v;
void check(int xa, int xb, int ya, int yb)
{
if(xb < xa || yb < ya)
return;
if(!((maxdr[xb][ya-1]-1 == yb && rightup[xb][ya-1] <= xa) || (maxst[xb][yb+1]+1 == ya && leftup[xb][yb+1] <= xa)))
return;
if(!((maxdwn[xa-1][yb]-1 == xb && downleft[xa-1][yb] <= ya) || (maxup[xb+1][yb]+1 == xa && upleft[xb+1][yb] <= ya)))
return;
v.push_back(((1LL * xa * 3010 + xb) * 3010 + ya) * 3010 + yb);
}
long long count_rectangles(vector<vector<int> > a)
{
int n = a.size();
int m = a[0].size();
long long ans = 0;
deque<int> d;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
while(!d.empty() && a[i][j] > a[i][d.back()])
d.pop_back();
if(d.empty())
maxst[i][j] = -1;
else
maxst[i][j] = d.back();
d.push_back(j);
}
d.clear();
for(int j = m - 1; j >= 0; --j)
{
while(!d.empty() && a[i][j] > a[i][d.back()])
d.pop_back();
if(d.empty())
maxdr[i][j] = -1;
else
maxdr[i][j] = d.back();
d.push_back(j);
}
d.clear();
}
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
while(!d.empty() && a[j][i] > a[d.back()][i])
d.pop_back();
if(d.empty())
maxup[j][i] = -1;
else
maxup[j][i] = d.back();
d.push_back(j);
}
d.clear();
for(int j = n-1; j >= 0; --j)
{
while(!d.empty() && a[j][i] > a[d.back()][i])
d.pop_back();
if(d.empty())
maxdwn[j][i] = -1;
else
maxdwn[j][i] = d.back();
d.push_back(j);
}
d.clear();
}
for(int j = 0; j < m; ++j)
{
for(int i = 0; i < n; ++i)
{
if(maxup[i][j] != -1)
{
if(j > 0 && maxup[i][j] == maxup[i][j-1])
upleft[i][j] = upleft[i][j-1];
else
if(j > 0 && i == maxdwn[maxup[i][j]][j-1])
upleft[i][j] = downleft[maxup[i][j]][j-1];
else
upleft[i][j] = j;
}
if(maxdwn[i][j] != -1)
{
if(j > 0 && maxdwn[i][j] == maxdwn[i][j-1])
downleft[i][j] = downleft[i][j-1];
else
if(j > 0 && i == maxup[maxdwn[i][j]][j-1])
downleft[i][j] = upleft[maxdwn[i][j]][j-1];
else
downleft[i][j] = j;
}
}
}
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
if(maxst[i][j] != -1)
{
if(i > 0 && maxst[i][j] == maxst[i-1][j])
leftup[i][j] = leftup[i-1][j];
else
if(i > 0 && j == maxdr[i-1][maxst[i][j]])
leftup[i][j] = rightup[i-1][maxst[i][j]];
else
leftup[i][j] = i;
}
if(maxdr[i][j] != -1)
{
if(i > 0 && maxdr[i][j] == maxdr[i-1][j])
rightup[i][j] = rightup[i-1][j];
else
if(i > 0 && j == maxst[i-1][maxdr[i][j]])
rightup[i][j] = leftup[i-1][maxdr[i][j]];
else
rightup[i][j] = i;
}
}
}
for(int i = 1; i + 1 < n; ++i)
for(int j = 1; j + 1 < m; ++j)
{
if(maxup[i+1][j] != -1 && maxst[i][j+1] != -1)
check(maxup[i+1][j]+1, i, maxst[i][j+1]+1, j);
if(maxup[i+1][j] != -1 && maxdr[i][j-1] != -1)
check(maxup[i+1][j]+1, i, j, maxdr[i][j-1]-1);
if(maxdwn[i-1][j] != -1 && maxst[i][j+1] != -1)
check(i, maxdwn[i-1][j]-1, maxst[i][j+1]+1, j);
if(maxdwn[i-1][j] != -1 && maxdr[i][j-1] != -1)
check(i, maxdwn[i-1][j]-1, j, maxdr[i][j-1]-1);
if(maxdwn[i-1][j] != -1 && maxdr[maxdwn[i-1][j]-1][j-1] != -1)
check(i, maxdwn[i-1][j]-1, j, maxdr[maxdwn[i-1][j]-1][j-1]-1);
if(maxdwn[i-1][j] != -1 && maxst[maxdwn[i-1][j]-1][j+1] != -1)
check(i, maxdwn[i-1][j]-1, maxst[maxdwn[i-1][j]-1][j+1]+1, j);
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
return v.size();
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:21:15: warning: unused variable 'ans' [-Wunused-variable]
long long ans = 0;
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
1400 KB |
Output is correct |
3 |
Correct |
5 ms |
1272 KB |
Output is correct |
4 |
Correct |
6 ms |
1400 KB |
Output is correct |
5 |
Correct |
5 ms |
1272 KB |
Output is correct |
6 |
Correct |
6 ms |
1272 KB |
Output is correct |
7 |
Correct |
5 ms |
1272 KB |
Output is correct |
8 |
Correct |
5 ms |
760 KB |
Output is correct |
9 |
Correct |
5 ms |
1272 KB |
Output is correct |
10 |
Correct |
5 ms |
1272 KB |
Output is correct |
11 |
Correct |
5 ms |
1272 KB |
Output is correct |
12 |
Correct |
5 ms |
1272 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
632 KB |
Output is correct |
15 |
Correct |
5 ms |
632 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
5 ms |
376 KB |
Output is correct |
19 |
Correct |
6 ms |
1272 KB |
Output is correct |
20 |
Correct |
5 ms |
1272 KB |
Output is correct |
21 |
Correct |
5 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
1400 KB |
Output is correct |
3 |
Correct |
5 ms |
1272 KB |
Output is correct |
4 |
Correct |
6 ms |
1400 KB |
Output is correct |
5 |
Correct |
5 ms |
1272 KB |
Output is correct |
6 |
Correct |
6 ms |
1272 KB |
Output is correct |
7 |
Correct |
5 ms |
1272 KB |
Output is correct |
8 |
Correct |
5 ms |
760 KB |
Output is correct |
9 |
Correct |
5 ms |
1272 KB |
Output is correct |
10 |
Correct |
5 ms |
1272 KB |
Output is correct |
11 |
Correct |
5 ms |
1272 KB |
Output is correct |
12 |
Correct |
5 ms |
1272 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
632 KB |
Output is correct |
15 |
Correct |
5 ms |
632 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
7 ms |
3448 KB |
Output is correct |
18 |
Correct |
8 ms |
3448 KB |
Output is correct |
19 |
Correct |
7 ms |
3448 KB |
Output is correct |
20 |
Correct |
7 ms |
3192 KB |
Output is correct |
21 |
Correct |
8 ms |
3196 KB |
Output is correct |
22 |
Correct |
7 ms |
3192 KB |
Output is correct |
23 |
Correct |
7 ms |
3192 KB |
Output is correct |
24 |
Correct |
6 ms |
3068 KB |
Output is correct |
25 |
Correct |
5 ms |
376 KB |
Output is correct |
26 |
Correct |
5 ms |
376 KB |
Output is correct |
27 |
Correct |
6 ms |
1272 KB |
Output is correct |
28 |
Correct |
5 ms |
1272 KB |
Output is correct |
29 |
Correct |
5 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
1400 KB |
Output is correct |
3 |
Correct |
5 ms |
1272 KB |
Output is correct |
4 |
Correct |
6 ms |
1400 KB |
Output is correct |
5 |
Correct |
5 ms |
1272 KB |
Output is correct |
6 |
Correct |
6 ms |
1272 KB |
Output is correct |
7 |
Correct |
5 ms |
1272 KB |
Output is correct |
8 |
Correct |
5 ms |
760 KB |
Output is correct |
9 |
Correct |
5 ms |
1272 KB |
Output is correct |
10 |
Correct |
5 ms |
1272 KB |
Output is correct |
11 |
Correct |
5 ms |
1272 KB |
Output is correct |
12 |
Correct |
5 ms |
1272 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
632 KB |
Output is correct |
15 |
Correct |
5 ms |
632 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
7 ms |
3448 KB |
Output is correct |
18 |
Correct |
8 ms |
3448 KB |
Output is correct |
19 |
Correct |
7 ms |
3448 KB |
Output is correct |
20 |
Correct |
7 ms |
3192 KB |
Output is correct |
21 |
Correct |
8 ms |
3196 KB |
Output is correct |
22 |
Correct |
7 ms |
3192 KB |
Output is correct |
23 |
Correct |
7 ms |
3192 KB |
Output is correct |
24 |
Correct |
6 ms |
3068 KB |
Output is correct |
25 |
Correct |
15 ms |
9720 KB |
Output is correct |
26 |
Correct |
15 ms |
9716 KB |
Output is correct |
27 |
Correct |
16 ms |
9972 KB |
Output is correct |
28 |
Correct |
15 ms |
8568 KB |
Output is correct |
29 |
Correct |
17 ms |
8824 KB |
Output is correct |
30 |
Correct |
17 ms |
9080 KB |
Output is correct |
31 |
Correct |
17 ms |
8952 KB |
Output is correct |
32 |
Correct |
17 ms |
8952 KB |
Output is correct |
33 |
Correct |
5 ms |
376 KB |
Output is correct |
34 |
Correct |
5 ms |
376 KB |
Output is correct |
35 |
Correct |
6 ms |
1272 KB |
Output is correct |
36 |
Correct |
5 ms |
1272 KB |
Output is correct |
37 |
Correct |
5 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
1400 KB |
Output is correct |
3 |
Correct |
5 ms |
1272 KB |
Output is correct |
4 |
Correct |
6 ms |
1400 KB |
Output is correct |
5 |
Correct |
5 ms |
1272 KB |
Output is correct |
6 |
Correct |
6 ms |
1272 KB |
Output is correct |
7 |
Correct |
5 ms |
1272 KB |
Output is correct |
8 |
Correct |
5 ms |
760 KB |
Output is correct |
9 |
Correct |
5 ms |
1272 KB |
Output is correct |
10 |
Correct |
5 ms |
1272 KB |
Output is correct |
11 |
Correct |
5 ms |
1272 KB |
Output is correct |
12 |
Correct |
5 ms |
1272 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
632 KB |
Output is correct |
15 |
Correct |
5 ms |
632 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
7 ms |
3448 KB |
Output is correct |
18 |
Correct |
8 ms |
3448 KB |
Output is correct |
19 |
Correct |
7 ms |
3448 KB |
Output is correct |
20 |
Correct |
7 ms |
3192 KB |
Output is correct |
21 |
Correct |
8 ms |
3196 KB |
Output is correct |
22 |
Correct |
7 ms |
3192 KB |
Output is correct |
23 |
Correct |
7 ms |
3192 KB |
Output is correct |
24 |
Correct |
6 ms |
3068 KB |
Output is correct |
25 |
Correct |
15 ms |
9720 KB |
Output is correct |
26 |
Correct |
15 ms |
9716 KB |
Output is correct |
27 |
Correct |
16 ms |
9972 KB |
Output is correct |
28 |
Correct |
15 ms |
8568 KB |
Output is correct |
29 |
Correct |
17 ms |
8824 KB |
Output is correct |
30 |
Correct |
17 ms |
9080 KB |
Output is correct |
31 |
Correct |
17 ms |
8952 KB |
Output is correct |
32 |
Correct |
17 ms |
8952 KB |
Output is correct |
33 |
Correct |
92 ms |
43256 KB |
Output is correct |
34 |
Correct |
94 ms |
43256 KB |
Output is correct |
35 |
Correct |
92 ms |
43260 KB |
Output is correct |
36 |
Correct |
86 ms |
43256 KB |
Output is correct |
37 |
Correct |
147 ms |
53596 KB |
Output is correct |
38 |
Correct |
143 ms |
53596 KB |
Output is correct |
39 |
Correct |
152 ms |
53852 KB |
Output is correct |
40 |
Correct |
142 ms |
51044 KB |
Output is correct |
41 |
Correct |
103 ms |
44064 KB |
Output is correct |
42 |
Correct |
153 ms |
45364 KB |
Output is correct |
43 |
Correct |
151 ms |
46056 KB |
Output is correct |
44 |
Correct |
164 ms |
47852 KB |
Output is correct |
45 |
Correct |
90 ms |
35404 KB |
Output is correct |
46 |
Correct |
76 ms |
24176 KB |
Output is correct |
47 |
Correct |
151 ms |
46908 KB |
Output is correct |
48 |
Correct |
165 ms |
47956 KB |
Output is correct |
49 |
Correct |
5 ms |
376 KB |
Output is correct |
50 |
Correct |
5 ms |
376 KB |
Output is correct |
51 |
Correct |
6 ms |
1272 KB |
Output is correct |
52 |
Correct |
5 ms |
1272 KB |
Output is correct |
53 |
Correct |
5 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
760 KB |
Output is correct |
2 |
Correct |
7 ms |
760 KB |
Output is correct |
3 |
Correct |
6 ms |
632 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
6 ms |
760 KB |
Output is correct |
6 |
Correct |
6 ms |
760 KB |
Output is correct |
7 |
Correct |
6 ms |
760 KB |
Output is correct |
8 |
Correct |
7 ms |
760 KB |
Output is correct |
9 |
Correct |
6 ms |
760 KB |
Output is correct |
10 |
Correct |
6 ms |
504 KB |
Output is correct |
11 |
Correct |
5 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
632 KB |
Output is correct |
2 |
Correct |
617 ms |
133432 KB |
Output is correct |
3 |
Correct |
1319 ms |
272760 KB |
Output is correct |
4 |
Correct |
1393 ms |
274124 KB |
Output is correct |
5 |
Correct |
1362 ms |
274032 KB |
Output is correct |
6 |
Correct |
543 ms |
127304 KB |
Output is correct |
7 |
Correct |
1033 ms |
253704 KB |
Output is correct |
8 |
Correct |
1102 ms |
257520 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
6 ms |
1272 KB |
Output is correct |
12 |
Correct |
5 ms |
1272 KB |
Output is correct |
13 |
Correct |
5 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
1400 KB |
Output is correct |
3 |
Correct |
5 ms |
1272 KB |
Output is correct |
4 |
Correct |
6 ms |
1400 KB |
Output is correct |
5 |
Correct |
5 ms |
1272 KB |
Output is correct |
6 |
Correct |
6 ms |
1272 KB |
Output is correct |
7 |
Correct |
5 ms |
1272 KB |
Output is correct |
8 |
Correct |
5 ms |
760 KB |
Output is correct |
9 |
Correct |
5 ms |
1272 KB |
Output is correct |
10 |
Correct |
5 ms |
1272 KB |
Output is correct |
11 |
Correct |
5 ms |
1272 KB |
Output is correct |
12 |
Correct |
5 ms |
1272 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
632 KB |
Output is correct |
15 |
Correct |
5 ms |
632 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
7 ms |
3448 KB |
Output is correct |
18 |
Correct |
8 ms |
3448 KB |
Output is correct |
19 |
Correct |
7 ms |
3448 KB |
Output is correct |
20 |
Correct |
7 ms |
3192 KB |
Output is correct |
21 |
Correct |
8 ms |
3196 KB |
Output is correct |
22 |
Correct |
7 ms |
3192 KB |
Output is correct |
23 |
Correct |
7 ms |
3192 KB |
Output is correct |
24 |
Correct |
6 ms |
3068 KB |
Output is correct |
25 |
Correct |
15 ms |
9720 KB |
Output is correct |
26 |
Correct |
15 ms |
9716 KB |
Output is correct |
27 |
Correct |
16 ms |
9972 KB |
Output is correct |
28 |
Correct |
15 ms |
8568 KB |
Output is correct |
29 |
Correct |
17 ms |
8824 KB |
Output is correct |
30 |
Correct |
17 ms |
9080 KB |
Output is correct |
31 |
Correct |
17 ms |
8952 KB |
Output is correct |
32 |
Correct |
17 ms |
8952 KB |
Output is correct |
33 |
Correct |
92 ms |
43256 KB |
Output is correct |
34 |
Correct |
94 ms |
43256 KB |
Output is correct |
35 |
Correct |
92 ms |
43260 KB |
Output is correct |
36 |
Correct |
86 ms |
43256 KB |
Output is correct |
37 |
Correct |
147 ms |
53596 KB |
Output is correct |
38 |
Correct |
143 ms |
53596 KB |
Output is correct |
39 |
Correct |
152 ms |
53852 KB |
Output is correct |
40 |
Correct |
142 ms |
51044 KB |
Output is correct |
41 |
Correct |
103 ms |
44064 KB |
Output is correct |
42 |
Correct |
153 ms |
45364 KB |
Output is correct |
43 |
Correct |
151 ms |
46056 KB |
Output is correct |
44 |
Correct |
164 ms |
47852 KB |
Output is correct |
45 |
Correct |
90 ms |
35404 KB |
Output is correct |
46 |
Correct |
76 ms |
24176 KB |
Output is correct |
47 |
Correct |
151 ms |
46908 KB |
Output is correct |
48 |
Correct |
165 ms |
47956 KB |
Output is correct |
49 |
Correct |
7 ms |
760 KB |
Output is correct |
50 |
Correct |
7 ms |
760 KB |
Output is correct |
51 |
Correct |
6 ms |
632 KB |
Output is correct |
52 |
Correct |
5 ms |
376 KB |
Output is correct |
53 |
Correct |
6 ms |
760 KB |
Output is correct |
54 |
Correct |
6 ms |
760 KB |
Output is correct |
55 |
Correct |
6 ms |
760 KB |
Output is correct |
56 |
Correct |
7 ms |
760 KB |
Output is correct |
57 |
Correct |
6 ms |
760 KB |
Output is correct |
58 |
Correct |
6 ms |
504 KB |
Output is correct |
59 |
Correct |
5 ms |
632 KB |
Output is correct |
60 |
Correct |
6 ms |
632 KB |
Output is correct |
61 |
Correct |
617 ms |
133432 KB |
Output is correct |
62 |
Correct |
1319 ms |
272760 KB |
Output is correct |
63 |
Correct |
1393 ms |
274124 KB |
Output is correct |
64 |
Correct |
1362 ms |
274032 KB |
Output is correct |
65 |
Correct |
543 ms |
127304 KB |
Output is correct |
66 |
Correct |
1033 ms |
253704 KB |
Output is correct |
67 |
Correct |
1102 ms |
257520 KB |
Output is correct |
68 |
Correct |
1220 ms |
283540 KB |
Output is correct |
69 |
Correct |
1271 ms |
283724 KB |
Output is correct |
70 |
Correct |
1113 ms |
283688 KB |
Output is correct |
71 |
Correct |
983 ms |
283568 KB |
Output is correct |
72 |
Correct |
2130 ms |
424504 KB |
Output is correct |
73 |
Correct |
1098 ms |
177932 KB |
Output is correct |
74 |
Correct |
1183 ms |
265936 KB |
Output is correct |
75 |
Correct |
1753 ms |
301316 KB |
Output is correct |
76 |
Correct |
1122 ms |
192912 KB |
Output is correct |
77 |
Correct |
1432 ms |
306876 KB |
Output is correct |
78 |
Correct |
1770 ms |
326296 KB |
Output is correct |
79 |
Correct |
987 ms |
185504 KB |
Output is correct |
80 |
Correct |
1682 ms |
326500 KB |
Output is correct |
81 |
Correct |
1657 ms |
318060 KB |
Output is correct |
82 |
Correct |
1435 ms |
320536 KB |
Output is correct |
83 |
Correct |
2192 ms |
424668 KB |
Output is correct |
84 |
Correct |
2128 ms |
424868 KB |
Output is correct |
85 |
Correct |
2348 ms |
424840 KB |
Output is correct |
86 |
Correct |
5 ms |
376 KB |
Output is correct |
87 |
Correct |
5 ms |
376 KB |
Output is correct |
88 |
Correct |
6 ms |
1272 KB |
Output is correct |
89 |
Correct |
5 ms |
1272 KB |
Output is correct |
90 |
Correct |
5 ms |
632 KB |
Output is correct |