#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2505;
int stk[N], to_l[N], to_r[N], w[N], last_v[N][N], last_h[N][N], c_v[N][N], c_h[N][N];
vector<int> lt[N][N], up[N][N];
void handle(int len) {
fill(to_l, to_l + len, -1);
fill(to_r, to_r + len, -1);
int z = 0;
for (int i = 0; i < len; i++) {
while (z > 0 && w[stk[z - 1]] <= w[i]) {
to_r[stk[--z]] = i;
}
stk[z++] = i;
}
z = 0;
for (int i = len - 1; i >= 0; i--) {
while (z > 0 && w[stk[z - 1]] <= w[i]) {
to_l[stk[--z]] = i;
}
stk[z++] = i;
}
}
ll count_rectangles(vector<vector<int>> a) {
// w[0] = 1;
// w[1] = 0;
// w[2] = 1;
// handle(3);
// for (int i = 0; i < 3; i++) {
// cout << to_l[i] << " ";
// }
// cout << "\n";
// for (int i = 0; i < 3; i++) {
// cout << to_r[i] << " ";
// }
// cout << "\n";
// return 0;
int n = a.size(),
m = a[0].size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
w[j] = a[i][j];
handle(m);
for (int j = 0; j < m; j++) {
if (to_l[j] != -1 && to_l[j] + 1 < j) {
lt[i][j - 1].push_back(to_l[j] + 1);
}
if (to_r[j] != -1 && to_l[to_r[j]] != j && j + 1 < to_r[j]) {
lt[i][to_r[j] - 1].push_back(j + 1);
}
}
}
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
w[i] = a[i][j];
}
handle(n);
for (int i = 0; i < n; i++) {
if (to_l[i] != -1 && to_l[i] + 1 < i) {
up[i - 1][j].push_back(to_l[i] + 1);
}
if (to_r[i] != -1 && to_l[to_r[i]] != i && i + 1 < to_r[i]) {
up[to_r[i] - 1][j].push_back(i + 1);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
last_v[i][j] = -1;
last_h[i][j] = -1;
}
}
ll ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int x : lt[i][j]) {
if (last_v[j][x] != i - 1)
c_v[j][x] = 0;
last_v[j][x] = i;
c_v[j][x]++;
}
for (int x : up[i][j]) {
if (last_h[i][x] != j - 1)
c_h[i][x] = 0;
last_h[i][x] = j;
c_h[i][x]++;
for (int y : lt[i][j]) {
if (i - c_v[j][y] + 1 <= x && j - c_h[i][x] + 1 <= y)
ans++;
}
}
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
282 ms |
295288 KB |
Output is correct |
2 |
Correct |
279 ms |
295288 KB |
Output is correct |
3 |
Correct |
297 ms |
295284 KB |
Output is correct |
4 |
Correct |
285 ms |
295288 KB |
Output is correct |
5 |
Correct |
276 ms |
295456 KB |
Output is correct |
6 |
Correct |
286 ms |
295568 KB |
Output is correct |
7 |
Correct |
277 ms |
295528 KB |
Output is correct |
8 |
Correct |
278 ms |
295416 KB |
Output is correct |
9 |
Correct |
278 ms |
295544 KB |
Output is correct |
10 |
Correct |
279 ms |
295672 KB |
Output is correct |
11 |
Correct |
279 ms |
295672 KB |
Output is correct |
12 |
Correct |
278 ms |
295684 KB |
Output is correct |
13 |
Correct |
278 ms |
295136 KB |
Output is correct |
14 |
Correct |
277 ms |
295188 KB |
Output is correct |
15 |
Correct |
275 ms |
295160 KB |
Output is correct |
16 |
Correct |
279 ms |
295216 KB |
Output is correct |
17 |
Correct |
278 ms |
295056 KB |
Output is correct |
18 |
Correct |
277 ms |
295160 KB |
Output is correct |
19 |
Correct |
278 ms |
295544 KB |
Output is correct |
20 |
Correct |
280 ms |
295324 KB |
Output is correct |
21 |
Correct |
276 ms |
295164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
282 ms |
295288 KB |
Output is correct |
2 |
Correct |
279 ms |
295288 KB |
Output is correct |
3 |
Correct |
297 ms |
295284 KB |
Output is correct |
4 |
Correct |
285 ms |
295288 KB |
Output is correct |
5 |
Correct |
276 ms |
295456 KB |
Output is correct |
6 |
Correct |
286 ms |
295568 KB |
Output is correct |
7 |
Correct |
277 ms |
295528 KB |
Output is correct |
8 |
Correct |
278 ms |
295416 KB |
Output is correct |
9 |
Correct |
278 ms |
295544 KB |
Output is correct |
10 |
Correct |
279 ms |
295672 KB |
Output is correct |
11 |
Correct |
279 ms |
295672 KB |
Output is correct |
12 |
Correct |
278 ms |
295684 KB |
Output is correct |
13 |
Correct |
278 ms |
295136 KB |
Output is correct |
14 |
Correct |
277 ms |
295188 KB |
Output is correct |
15 |
Correct |
275 ms |
295160 KB |
Output is correct |
16 |
Correct |
279 ms |
295216 KB |
Output is correct |
17 |
Correct |
279 ms |
296028 KB |
Output is correct |
18 |
Correct |
279 ms |
296056 KB |
Output is correct |
19 |
Correct |
279 ms |
295928 KB |
Output is correct |
20 |
Correct |
280 ms |
296620 KB |
Output is correct |
21 |
Correct |
280 ms |
296696 KB |
Output is correct |
22 |
Correct |
282 ms |
296744 KB |
Output is correct |
23 |
Correct |
280 ms |
296696 KB |
Output is correct |
24 |
Correct |
282 ms |
296312 KB |
Output is correct |
25 |
Correct |
278 ms |
295056 KB |
Output is correct |
26 |
Correct |
277 ms |
295160 KB |
Output is correct |
27 |
Correct |
278 ms |
295544 KB |
Output is correct |
28 |
Correct |
280 ms |
295324 KB |
Output is correct |
29 |
Correct |
276 ms |
295164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
282 ms |
295288 KB |
Output is correct |
2 |
Correct |
279 ms |
295288 KB |
Output is correct |
3 |
Correct |
297 ms |
295284 KB |
Output is correct |
4 |
Correct |
285 ms |
295288 KB |
Output is correct |
5 |
Correct |
276 ms |
295456 KB |
Output is correct |
6 |
Correct |
286 ms |
295568 KB |
Output is correct |
7 |
Correct |
277 ms |
295528 KB |
Output is correct |
8 |
Correct |
278 ms |
295416 KB |
Output is correct |
9 |
Correct |
278 ms |
295544 KB |
Output is correct |
10 |
Correct |
279 ms |
295672 KB |
Output is correct |
11 |
Correct |
279 ms |
295672 KB |
Output is correct |
12 |
Correct |
278 ms |
295684 KB |
Output is correct |
13 |
Correct |
278 ms |
295136 KB |
Output is correct |
14 |
Correct |
277 ms |
295188 KB |
Output is correct |
15 |
Correct |
275 ms |
295160 KB |
Output is correct |
16 |
Correct |
279 ms |
295216 KB |
Output is correct |
17 |
Correct |
279 ms |
296028 KB |
Output is correct |
18 |
Correct |
279 ms |
296056 KB |
Output is correct |
19 |
Correct |
279 ms |
295928 KB |
Output is correct |
20 |
Correct |
280 ms |
296620 KB |
Output is correct |
21 |
Correct |
280 ms |
296696 KB |
Output is correct |
22 |
Correct |
282 ms |
296744 KB |
Output is correct |
23 |
Correct |
280 ms |
296696 KB |
Output is correct |
24 |
Correct |
282 ms |
296312 KB |
Output is correct |
25 |
Correct |
286 ms |
297976 KB |
Output is correct |
26 |
Correct |
284 ms |
297976 KB |
Output is correct |
27 |
Correct |
285 ms |
298168 KB |
Output is correct |
28 |
Correct |
291 ms |
299980 KB |
Output is correct |
29 |
Correct |
297 ms |
300408 KB |
Output is correct |
30 |
Correct |
295 ms |
300576 KB |
Output is correct |
31 |
Correct |
295 ms |
300332 KB |
Output is correct |
32 |
Correct |
294 ms |
300408 KB |
Output is correct |
33 |
Correct |
278 ms |
295056 KB |
Output is correct |
34 |
Correct |
277 ms |
295160 KB |
Output is correct |
35 |
Correct |
278 ms |
295544 KB |
Output is correct |
36 |
Correct |
280 ms |
295324 KB |
Output is correct |
37 |
Correct |
276 ms |
295164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
282 ms |
295288 KB |
Output is correct |
2 |
Correct |
279 ms |
295288 KB |
Output is correct |
3 |
Correct |
297 ms |
295284 KB |
Output is correct |
4 |
Correct |
285 ms |
295288 KB |
Output is correct |
5 |
Correct |
276 ms |
295456 KB |
Output is correct |
6 |
Correct |
286 ms |
295568 KB |
Output is correct |
7 |
Correct |
277 ms |
295528 KB |
Output is correct |
8 |
Correct |
278 ms |
295416 KB |
Output is correct |
9 |
Correct |
278 ms |
295544 KB |
Output is correct |
10 |
Correct |
279 ms |
295672 KB |
Output is correct |
11 |
Correct |
279 ms |
295672 KB |
Output is correct |
12 |
Correct |
278 ms |
295684 KB |
Output is correct |
13 |
Correct |
278 ms |
295136 KB |
Output is correct |
14 |
Correct |
277 ms |
295188 KB |
Output is correct |
15 |
Correct |
275 ms |
295160 KB |
Output is correct |
16 |
Correct |
279 ms |
295216 KB |
Output is correct |
17 |
Correct |
279 ms |
296028 KB |
Output is correct |
18 |
Correct |
279 ms |
296056 KB |
Output is correct |
19 |
Correct |
279 ms |
295928 KB |
Output is correct |
20 |
Correct |
280 ms |
296620 KB |
Output is correct |
21 |
Correct |
280 ms |
296696 KB |
Output is correct |
22 |
Correct |
282 ms |
296744 KB |
Output is correct |
23 |
Correct |
280 ms |
296696 KB |
Output is correct |
24 |
Correct |
282 ms |
296312 KB |
Output is correct |
25 |
Correct |
286 ms |
297976 KB |
Output is correct |
26 |
Correct |
284 ms |
297976 KB |
Output is correct |
27 |
Correct |
285 ms |
298168 KB |
Output is correct |
28 |
Correct |
291 ms |
299980 KB |
Output is correct |
29 |
Correct |
297 ms |
300408 KB |
Output is correct |
30 |
Correct |
295 ms |
300576 KB |
Output is correct |
31 |
Correct |
295 ms |
300332 KB |
Output is correct |
32 |
Correct |
294 ms |
300408 KB |
Output is correct |
33 |
Correct |
438 ms |
321912 KB |
Output is correct |
34 |
Correct |
345 ms |
328312 KB |
Output is correct |
35 |
Correct |
381 ms |
328184 KB |
Output is correct |
36 |
Correct |
396 ms |
334436 KB |
Output is correct |
37 |
Correct |
336 ms |
317432 KB |
Output is correct |
38 |
Correct |
367 ms |
317440 KB |
Output is correct |
39 |
Correct |
342 ms |
317732 KB |
Output is correct |
40 |
Correct |
334 ms |
316708 KB |
Output is correct |
41 |
Correct |
379 ms |
322808 KB |
Output is correct |
42 |
Correct |
398 ms |
325332 KB |
Output is correct |
43 |
Correct |
476 ms |
333116 KB |
Output is correct |
44 |
Correct |
479 ms |
334932 KB |
Output is correct |
45 |
Correct |
381 ms |
319544 KB |
Output is correct |
46 |
Correct |
378 ms |
318388 KB |
Output is correct |
47 |
Correct |
460 ms |
331636 KB |
Output is correct |
48 |
Correct |
462 ms |
332568 KB |
Output is correct |
49 |
Correct |
278 ms |
295056 KB |
Output is correct |
50 |
Correct |
277 ms |
295160 KB |
Output is correct |
51 |
Correct |
278 ms |
295544 KB |
Output is correct |
52 |
Correct |
280 ms |
295324 KB |
Output is correct |
53 |
Correct |
276 ms |
295164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
279 ms |
295468 KB |
Output is correct |
2 |
Correct |
278 ms |
295380 KB |
Output is correct |
3 |
Correct |
287 ms |
295276 KB |
Output is correct |
4 |
Correct |
279 ms |
295192 KB |
Output is correct |
5 |
Correct |
301 ms |
313208 KB |
Output is correct |
6 |
Correct |
297 ms |
313124 KB |
Output is correct |
7 |
Correct |
334 ms |
313208 KB |
Output is correct |
8 |
Correct |
311 ms |
312220 KB |
Output is correct |
9 |
Correct |
298 ms |
311544 KB |
Output is correct |
10 |
Correct |
288 ms |
305244 KB |
Output is correct |
11 |
Correct |
294 ms |
310540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
278 ms |
295212 KB |
Output is correct |
2 |
Correct |
892 ms |
410900 KB |
Output is correct |
3 |
Correct |
1611 ms |
513124 KB |
Output is correct |
4 |
Correct |
1601 ms |
514632 KB |
Output is correct |
5 |
Correct |
1597 ms |
514860 KB |
Output is correct |
6 |
Correct |
417 ms |
349688 KB |
Output is correct |
7 |
Correct |
570 ms |
393596 KB |
Output is correct |
8 |
Correct |
586 ms |
396408 KB |
Output is correct |
9 |
Correct |
278 ms |
295056 KB |
Output is correct |
10 |
Correct |
277 ms |
295160 KB |
Output is correct |
11 |
Correct |
278 ms |
295544 KB |
Output is correct |
12 |
Correct |
280 ms |
295324 KB |
Output is correct |
13 |
Correct |
276 ms |
295164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
282 ms |
295288 KB |
Output is correct |
2 |
Correct |
279 ms |
295288 KB |
Output is correct |
3 |
Correct |
297 ms |
295284 KB |
Output is correct |
4 |
Correct |
285 ms |
295288 KB |
Output is correct |
5 |
Correct |
276 ms |
295456 KB |
Output is correct |
6 |
Correct |
286 ms |
295568 KB |
Output is correct |
7 |
Correct |
277 ms |
295528 KB |
Output is correct |
8 |
Correct |
278 ms |
295416 KB |
Output is correct |
9 |
Correct |
278 ms |
295544 KB |
Output is correct |
10 |
Correct |
279 ms |
295672 KB |
Output is correct |
11 |
Correct |
279 ms |
295672 KB |
Output is correct |
12 |
Correct |
278 ms |
295684 KB |
Output is correct |
13 |
Correct |
278 ms |
295136 KB |
Output is correct |
14 |
Correct |
277 ms |
295188 KB |
Output is correct |
15 |
Correct |
275 ms |
295160 KB |
Output is correct |
16 |
Correct |
279 ms |
295216 KB |
Output is correct |
17 |
Correct |
279 ms |
296028 KB |
Output is correct |
18 |
Correct |
279 ms |
296056 KB |
Output is correct |
19 |
Correct |
279 ms |
295928 KB |
Output is correct |
20 |
Correct |
280 ms |
296620 KB |
Output is correct |
21 |
Correct |
280 ms |
296696 KB |
Output is correct |
22 |
Correct |
282 ms |
296744 KB |
Output is correct |
23 |
Correct |
280 ms |
296696 KB |
Output is correct |
24 |
Correct |
282 ms |
296312 KB |
Output is correct |
25 |
Correct |
286 ms |
297976 KB |
Output is correct |
26 |
Correct |
284 ms |
297976 KB |
Output is correct |
27 |
Correct |
285 ms |
298168 KB |
Output is correct |
28 |
Correct |
291 ms |
299980 KB |
Output is correct |
29 |
Correct |
297 ms |
300408 KB |
Output is correct |
30 |
Correct |
295 ms |
300576 KB |
Output is correct |
31 |
Correct |
295 ms |
300332 KB |
Output is correct |
32 |
Correct |
294 ms |
300408 KB |
Output is correct |
33 |
Correct |
438 ms |
321912 KB |
Output is correct |
34 |
Correct |
345 ms |
328312 KB |
Output is correct |
35 |
Correct |
381 ms |
328184 KB |
Output is correct |
36 |
Correct |
396 ms |
334436 KB |
Output is correct |
37 |
Correct |
336 ms |
317432 KB |
Output is correct |
38 |
Correct |
367 ms |
317440 KB |
Output is correct |
39 |
Correct |
342 ms |
317732 KB |
Output is correct |
40 |
Correct |
334 ms |
316708 KB |
Output is correct |
41 |
Correct |
379 ms |
322808 KB |
Output is correct |
42 |
Correct |
398 ms |
325332 KB |
Output is correct |
43 |
Correct |
476 ms |
333116 KB |
Output is correct |
44 |
Correct |
479 ms |
334932 KB |
Output is correct |
45 |
Correct |
381 ms |
319544 KB |
Output is correct |
46 |
Correct |
378 ms |
318388 KB |
Output is correct |
47 |
Correct |
460 ms |
331636 KB |
Output is correct |
48 |
Correct |
462 ms |
332568 KB |
Output is correct |
49 |
Correct |
279 ms |
295468 KB |
Output is correct |
50 |
Correct |
278 ms |
295380 KB |
Output is correct |
51 |
Correct |
287 ms |
295276 KB |
Output is correct |
52 |
Correct |
279 ms |
295192 KB |
Output is correct |
53 |
Correct |
301 ms |
313208 KB |
Output is correct |
54 |
Correct |
297 ms |
313124 KB |
Output is correct |
55 |
Correct |
334 ms |
313208 KB |
Output is correct |
56 |
Correct |
311 ms |
312220 KB |
Output is correct |
57 |
Correct |
298 ms |
311544 KB |
Output is correct |
58 |
Correct |
288 ms |
305244 KB |
Output is correct |
59 |
Correct |
294 ms |
310540 KB |
Output is correct |
60 |
Correct |
278 ms |
295212 KB |
Output is correct |
61 |
Correct |
892 ms |
410900 KB |
Output is correct |
62 |
Correct |
1611 ms |
513124 KB |
Output is correct |
63 |
Correct |
1601 ms |
514632 KB |
Output is correct |
64 |
Correct |
1597 ms |
514860 KB |
Output is correct |
65 |
Correct |
417 ms |
349688 KB |
Output is correct |
66 |
Correct |
570 ms |
393596 KB |
Output is correct |
67 |
Correct |
586 ms |
396408 KB |
Output is correct |
68 |
Execution timed out |
5045 ms |
512500 KB |
Time limit exceeded |
69 |
Halted |
0 ms |
0 KB |
- |