#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
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], t[N];
vector<int> lt[N][N], up[N][N];
pair<int, int> ls[N];
void upd(int x, int y) {
for (; x < N; x |= x + 1)
t[x] += y;
}
int que(int x) {
int s = 0;
for (; x >= 0; x = (x & (x + 1)) - 1)
s += t[x];
return s;
}
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) {
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]++;
}
if (lt[i][j].empty())
continue;
sort(all(lt[i][j]));
int p_lt = lt[i][j].size() - 1;
int z = 0;
for (int x : up[i][j]) {
ls[z++] = {j - c_h[i][x] + 1, x};
}
sort(ls, ls + z);
for (int k = z - 1; k >= 0; k--) {
while (p_lt >= 0 && lt[i][j][p_lt] >= ls[k].first) {
upd(i - c_v[j][lt[i][j][p_lt]] + 1, 1);
p_lt--;
}
ans += que(ls[k].second);
}
for (int k = p_lt + 1; k < lt[i][j].size(); k++) {
upd(i - c_v[j][lt[i][j][k]] + 1, -1);
}
}
}
return ans;
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:130:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int k = p_lt + 1; k < lt[i][j].size(); k++) {
~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
275 ms |
295160 KB |
Output is correct |
2 |
Correct |
274 ms |
295484 KB |
Output is correct |
3 |
Correct |
275 ms |
295416 KB |
Output is correct |
4 |
Correct |
275 ms |
295416 KB |
Output is correct |
5 |
Correct |
276 ms |
295356 KB |
Output is correct |
6 |
Correct |
277 ms |
295544 KB |
Output is correct |
7 |
Correct |
276 ms |
295524 KB |
Output is correct |
8 |
Correct |
275 ms |
295496 KB |
Output is correct |
9 |
Correct |
277 ms |
295548 KB |
Output is correct |
10 |
Correct |
278 ms |
295544 KB |
Output is correct |
11 |
Correct |
275 ms |
295644 KB |
Output is correct |
12 |
Correct |
277 ms |
295620 KB |
Output is correct |
13 |
Correct |
276 ms |
295032 KB |
Output is correct |
14 |
Correct |
274 ms |
295252 KB |
Output is correct |
15 |
Correct |
274 ms |
295160 KB |
Output is correct |
16 |
Correct |
275 ms |
295228 KB |
Output is correct |
17 |
Correct |
276 ms |
295160 KB |
Output is correct |
18 |
Correct |
276 ms |
295032 KB |
Output is correct |
19 |
Correct |
275 ms |
295648 KB |
Output is correct |
20 |
Correct |
276 ms |
295288 KB |
Output is correct |
21 |
Correct |
278 ms |
295160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
275 ms |
295160 KB |
Output is correct |
2 |
Correct |
274 ms |
295484 KB |
Output is correct |
3 |
Correct |
275 ms |
295416 KB |
Output is correct |
4 |
Correct |
275 ms |
295416 KB |
Output is correct |
5 |
Correct |
276 ms |
295356 KB |
Output is correct |
6 |
Correct |
277 ms |
295544 KB |
Output is correct |
7 |
Correct |
276 ms |
295524 KB |
Output is correct |
8 |
Correct |
275 ms |
295496 KB |
Output is correct |
9 |
Correct |
277 ms |
295548 KB |
Output is correct |
10 |
Correct |
278 ms |
295544 KB |
Output is correct |
11 |
Correct |
275 ms |
295644 KB |
Output is correct |
12 |
Correct |
277 ms |
295620 KB |
Output is correct |
13 |
Correct |
276 ms |
295032 KB |
Output is correct |
14 |
Correct |
274 ms |
295252 KB |
Output is correct |
15 |
Correct |
274 ms |
295160 KB |
Output is correct |
16 |
Correct |
275 ms |
295228 KB |
Output is correct |
17 |
Correct |
278 ms |
296128 KB |
Output is correct |
18 |
Correct |
278 ms |
295928 KB |
Output is correct |
19 |
Correct |
277 ms |
296056 KB |
Output is correct |
20 |
Correct |
280 ms |
296568 KB |
Output is correct |
21 |
Correct |
279 ms |
296824 KB |
Output is correct |
22 |
Correct |
302 ms |
296696 KB |
Output is correct |
23 |
Correct |
279 ms |
296704 KB |
Output is correct |
24 |
Correct |
279 ms |
296312 KB |
Output is correct |
25 |
Correct |
276 ms |
295160 KB |
Output is correct |
26 |
Correct |
276 ms |
295032 KB |
Output is correct |
27 |
Correct |
275 ms |
295648 KB |
Output is correct |
28 |
Correct |
276 ms |
295288 KB |
Output is correct |
29 |
Correct |
278 ms |
295160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
275 ms |
295160 KB |
Output is correct |
2 |
Correct |
274 ms |
295484 KB |
Output is correct |
3 |
Correct |
275 ms |
295416 KB |
Output is correct |
4 |
Correct |
275 ms |
295416 KB |
Output is correct |
5 |
Correct |
276 ms |
295356 KB |
Output is correct |
6 |
Correct |
277 ms |
295544 KB |
Output is correct |
7 |
Correct |
276 ms |
295524 KB |
Output is correct |
8 |
Correct |
275 ms |
295496 KB |
Output is correct |
9 |
Correct |
277 ms |
295548 KB |
Output is correct |
10 |
Correct |
278 ms |
295544 KB |
Output is correct |
11 |
Correct |
275 ms |
295644 KB |
Output is correct |
12 |
Correct |
277 ms |
295620 KB |
Output is correct |
13 |
Correct |
276 ms |
295032 KB |
Output is correct |
14 |
Correct |
274 ms |
295252 KB |
Output is correct |
15 |
Correct |
274 ms |
295160 KB |
Output is correct |
16 |
Correct |
275 ms |
295228 KB |
Output is correct |
17 |
Correct |
278 ms |
296128 KB |
Output is correct |
18 |
Correct |
278 ms |
295928 KB |
Output is correct |
19 |
Correct |
277 ms |
296056 KB |
Output is correct |
20 |
Correct |
280 ms |
296568 KB |
Output is correct |
21 |
Correct |
279 ms |
296824 KB |
Output is correct |
22 |
Correct |
302 ms |
296696 KB |
Output is correct |
23 |
Correct |
279 ms |
296704 KB |
Output is correct |
24 |
Correct |
279 ms |
296312 KB |
Output is correct |
25 |
Correct |
283 ms |
298060 KB |
Output is correct |
26 |
Correct |
284 ms |
297976 KB |
Output is correct |
27 |
Correct |
292 ms |
298160 KB |
Output is correct |
28 |
Correct |
308 ms |
299912 KB |
Output is correct |
29 |
Correct |
291 ms |
300556 KB |
Output is correct |
30 |
Correct |
292 ms |
300792 KB |
Output is correct |
31 |
Correct |
293 ms |
300408 KB |
Output is correct |
32 |
Correct |
294 ms |
300408 KB |
Output is correct |
33 |
Correct |
276 ms |
295160 KB |
Output is correct |
34 |
Correct |
276 ms |
295032 KB |
Output is correct |
35 |
Correct |
275 ms |
295648 KB |
Output is correct |
36 |
Correct |
276 ms |
295288 KB |
Output is correct |
37 |
Correct |
278 ms |
295160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
275 ms |
295160 KB |
Output is correct |
2 |
Correct |
274 ms |
295484 KB |
Output is correct |
3 |
Correct |
275 ms |
295416 KB |
Output is correct |
4 |
Correct |
275 ms |
295416 KB |
Output is correct |
5 |
Correct |
276 ms |
295356 KB |
Output is correct |
6 |
Correct |
277 ms |
295544 KB |
Output is correct |
7 |
Correct |
276 ms |
295524 KB |
Output is correct |
8 |
Correct |
275 ms |
295496 KB |
Output is correct |
9 |
Correct |
277 ms |
295548 KB |
Output is correct |
10 |
Correct |
278 ms |
295544 KB |
Output is correct |
11 |
Correct |
275 ms |
295644 KB |
Output is correct |
12 |
Correct |
277 ms |
295620 KB |
Output is correct |
13 |
Correct |
276 ms |
295032 KB |
Output is correct |
14 |
Correct |
274 ms |
295252 KB |
Output is correct |
15 |
Correct |
274 ms |
295160 KB |
Output is correct |
16 |
Correct |
275 ms |
295228 KB |
Output is correct |
17 |
Correct |
278 ms |
296128 KB |
Output is correct |
18 |
Correct |
278 ms |
295928 KB |
Output is correct |
19 |
Correct |
277 ms |
296056 KB |
Output is correct |
20 |
Correct |
280 ms |
296568 KB |
Output is correct |
21 |
Correct |
279 ms |
296824 KB |
Output is correct |
22 |
Correct |
302 ms |
296696 KB |
Output is correct |
23 |
Correct |
279 ms |
296704 KB |
Output is correct |
24 |
Correct |
279 ms |
296312 KB |
Output is correct |
25 |
Correct |
283 ms |
298060 KB |
Output is correct |
26 |
Correct |
284 ms |
297976 KB |
Output is correct |
27 |
Correct |
292 ms |
298160 KB |
Output is correct |
28 |
Correct |
308 ms |
299912 KB |
Output is correct |
29 |
Correct |
291 ms |
300556 KB |
Output is correct |
30 |
Correct |
292 ms |
300792 KB |
Output is correct |
31 |
Correct |
293 ms |
300408 KB |
Output is correct |
32 |
Correct |
294 ms |
300408 KB |
Output is correct |
33 |
Correct |
335 ms |
322012 KB |
Output is correct |
34 |
Correct |
354 ms |
328148 KB |
Output is correct |
35 |
Correct |
378 ms |
328248 KB |
Output is correct |
36 |
Correct |
393 ms |
334328 KB |
Output is correct |
37 |
Correct |
366 ms |
317612 KB |
Output is correct |
38 |
Correct |
365 ms |
317484 KB |
Output is correct |
39 |
Correct |
367 ms |
317668 KB |
Output is correct |
40 |
Correct |
363 ms |
316592 KB |
Output is correct |
41 |
Correct |
381 ms |
322680 KB |
Output is correct |
42 |
Correct |
407 ms |
325340 KB |
Output is correct |
43 |
Correct |
477 ms |
332992 KB |
Output is correct |
44 |
Correct |
487 ms |
334976 KB |
Output is correct |
45 |
Correct |
382 ms |
319480 KB |
Output is correct |
46 |
Correct |
382 ms |
318232 KB |
Output is correct |
47 |
Correct |
468 ms |
331640 KB |
Output is correct |
48 |
Correct |
475 ms |
332692 KB |
Output is correct |
49 |
Correct |
276 ms |
295160 KB |
Output is correct |
50 |
Correct |
276 ms |
295032 KB |
Output is correct |
51 |
Correct |
275 ms |
295648 KB |
Output is correct |
52 |
Correct |
276 ms |
295288 KB |
Output is correct |
53 |
Correct |
278 ms |
295160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
285 ms |
295340 KB |
Output is correct |
2 |
Correct |
314 ms |
295416 KB |
Output is correct |
3 |
Correct |
275 ms |
295160 KB |
Output is correct |
4 |
Correct |
275 ms |
295032 KB |
Output is correct |
5 |
Correct |
298 ms |
313344 KB |
Output is correct |
6 |
Correct |
295 ms |
313124 KB |
Output is correct |
7 |
Correct |
296 ms |
313256 KB |
Output is correct |
8 |
Correct |
293 ms |
312312 KB |
Output is correct |
9 |
Correct |
293 ms |
311544 KB |
Output is correct |
10 |
Correct |
285 ms |
305336 KB |
Output is correct |
11 |
Correct |
297 ms |
310576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
293 ms |
295284 KB |
Output is correct |
2 |
Correct |
897 ms |
406136 KB |
Output is correct |
3 |
Correct |
1666 ms |
513784 KB |
Output is correct |
4 |
Correct |
1778 ms |
515288 KB |
Output is correct |
5 |
Correct |
1667 ms |
515504 KB |
Output is correct |
6 |
Correct |
431 ms |
344056 KB |
Output is correct |
7 |
Correct |
592 ms |
394104 KB |
Output is correct |
8 |
Correct |
587 ms |
397048 KB |
Output is correct |
9 |
Correct |
276 ms |
295160 KB |
Output is correct |
10 |
Correct |
276 ms |
295032 KB |
Output is correct |
11 |
Correct |
275 ms |
295648 KB |
Output is correct |
12 |
Correct |
276 ms |
295288 KB |
Output is correct |
13 |
Correct |
278 ms |
295160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
275 ms |
295160 KB |
Output is correct |
2 |
Correct |
274 ms |
295484 KB |
Output is correct |
3 |
Correct |
275 ms |
295416 KB |
Output is correct |
4 |
Correct |
275 ms |
295416 KB |
Output is correct |
5 |
Correct |
276 ms |
295356 KB |
Output is correct |
6 |
Correct |
277 ms |
295544 KB |
Output is correct |
7 |
Correct |
276 ms |
295524 KB |
Output is correct |
8 |
Correct |
275 ms |
295496 KB |
Output is correct |
9 |
Correct |
277 ms |
295548 KB |
Output is correct |
10 |
Correct |
278 ms |
295544 KB |
Output is correct |
11 |
Correct |
275 ms |
295644 KB |
Output is correct |
12 |
Correct |
277 ms |
295620 KB |
Output is correct |
13 |
Correct |
276 ms |
295032 KB |
Output is correct |
14 |
Correct |
274 ms |
295252 KB |
Output is correct |
15 |
Correct |
274 ms |
295160 KB |
Output is correct |
16 |
Correct |
275 ms |
295228 KB |
Output is correct |
17 |
Correct |
278 ms |
296128 KB |
Output is correct |
18 |
Correct |
278 ms |
295928 KB |
Output is correct |
19 |
Correct |
277 ms |
296056 KB |
Output is correct |
20 |
Correct |
280 ms |
296568 KB |
Output is correct |
21 |
Correct |
279 ms |
296824 KB |
Output is correct |
22 |
Correct |
302 ms |
296696 KB |
Output is correct |
23 |
Correct |
279 ms |
296704 KB |
Output is correct |
24 |
Correct |
279 ms |
296312 KB |
Output is correct |
25 |
Correct |
283 ms |
298060 KB |
Output is correct |
26 |
Correct |
284 ms |
297976 KB |
Output is correct |
27 |
Correct |
292 ms |
298160 KB |
Output is correct |
28 |
Correct |
308 ms |
299912 KB |
Output is correct |
29 |
Correct |
291 ms |
300556 KB |
Output is correct |
30 |
Correct |
292 ms |
300792 KB |
Output is correct |
31 |
Correct |
293 ms |
300408 KB |
Output is correct |
32 |
Correct |
294 ms |
300408 KB |
Output is correct |
33 |
Correct |
335 ms |
322012 KB |
Output is correct |
34 |
Correct |
354 ms |
328148 KB |
Output is correct |
35 |
Correct |
378 ms |
328248 KB |
Output is correct |
36 |
Correct |
393 ms |
334328 KB |
Output is correct |
37 |
Correct |
366 ms |
317612 KB |
Output is correct |
38 |
Correct |
365 ms |
317484 KB |
Output is correct |
39 |
Correct |
367 ms |
317668 KB |
Output is correct |
40 |
Correct |
363 ms |
316592 KB |
Output is correct |
41 |
Correct |
381 ms |
322680 KB |
Output is correct |
42 |
Correct |
407 ms |
325340 KB |
Output is correct |
43 |
Correct |
477 ms |
332992 KB |
Output is correct |
44 |
Correct |
487 ms |
334976 KB |
Output is correct |
45 |
Correct |
382 ms |
319480 KB |
Output is correct |
46 |
Correct |
382 ms |
318232 KB |
Output is correct |
47 |
Correct |
468 ms |
331640 KB |
Output is correct |
48 |
Correct |
475 ms |
332692 KB |
Output is correct |
49 |
Correct |
285 ms |
295340 KB |
Output is correct |
50 |
Correct |
314 ms |
295416 KB |
Output is correct |
51 |
Correct |
275 ms |
295160 KB |
Output is correct |
52 |
Correct |
275 ms |
295032 KB |
Output is correct |
53 |
Correct |
298 ms |
313344 KB |
Output is correct |
54 |
Correct |
295 ms |
313124 KB |
Output is correct |
55 |
Correct |
296 ms |
313256 KB |
Output is correct |
56 |
Correct |
293 ms |
312312 KB |
Output is correct |
57 |
Correct |
293 ms |
311544 KB |
Output is correct |
58 |
Correct |
285 ms |
305336 KB |
Output is correct |
59 |
Correct |
297 ms |
310576 KB |
Output is correct |
60 |
Correct |
293 ms |
295284 KB |
Output is correct |
61 |
Correct |
897 ms |
406136 KB |
Output is correct |
62 |
Correct |
1666 ms |
513784 KB |
Output is correct |
63 |
Correct |
1778 ms |
515288 KB |
Output is correct |
64 |
Correct |
1667 ms |
515504 KB |
Output is correct |
65 |
Correct |
431 ms |
344056 KB |
Output is correct |
66 |
Correct |
592 ms |
394104 KB |
Output is correct |
67 |
Correct |
587 ms |
397048 KB |
Output is correct |
68 |
Correct |
977 ms |
469504 KB |
Output is correct |
69 |
Correct |
1362 ms |
594108 KB |
Output is correct |
70 |
Correct |
1892 ms |
593476 KB |
Output is correct |
71 |
Correct |
2107 ms |
673244 KB |
Output is correct |
72 |
Correct |
1459 ms |
509552 KB |
Output is correct |
73 |
Correct |
1933 ms |
520408 KB |
Output is correct |
74 |
Correct |
2084 ms |
552964 KB |
Output is correct |
75 |
Correct |
3078 ms |
650288 KB |
Output is correct |
76 |
Correct |
2001 ms |
539496 KB |
Output is correct |
77 |
Correct |
2595 ms |
615928 KB |
Output is correct |
78 |
Correct |
3255 ms |
679168 KB |
Output is correct |
79 |
Correct |
1910 ms |
509336 KB |
Output is correct |
80 |
Correct |
3042 ms |
652956 KB |
Output is correct |
81 |
Correct |
2946 ms |
642296 KB |
Output is correct |
82 |
Correct |
994 ms |
443396 KB |
Output is correct |
83 |
Correct |
1458 ms |
510404 KB |
Output is correct |
84 |
Correct |
1459 ms |
510584 KB |
Output is correct |
85 |
Correct |
1475 ms |
510512 KB |
Output is correct |
86 |
Correct |
276 ms |
295160 KB |
Output is correct |
87 |
Correct |
276 ms |
295032 KB |
Output is correct |
88 |
Correct |
275 ms |
295648 KB |
Output is correct |
89 |
Correct |
276 ms |
295288 KB |
Output is correct |
90 |
Correct |
278 ms |
295160 KB |
Output is correct |