#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ar array
const int mxN=2.5e3;
int n, m, l[mxN], r[mxN], ft[mxN+1];
vector<ar<int, 2>> p[mxN][mxN][2];
vector<int> d[mxN][mxN];
void upd(int i, int x) {
for(++i; i<=m; i+=i&-i)
ft[i]+=x;
}
int qry(int i) {
int r=0;
for(; i; i-=i&-i)
r+=ft[i];
return r;
}
void gr(vector<vector<int>> a, int b) {
int n=a.size(), m=a[0].size();
vector<ar<int, 3>> s;
for(int i=0; i<n; ++i) {
for(int j=0; j<m; ++j) {
l[j]=j-1;
while(~l[j]&&a[i][l[j]]<=a[i][j])
l[j]=l[l[j]];
}
for(int j=m-1; ~j; --j) {
r[j]=j+1;
while(r[j]<m&&a[i][r[j]]<=a[i][j])
r[j]=r[r[j]];
if(~l[j]&&r[j]<m)
d[l[j]+1][r[j]-1].push_back(i);
}
}
for(int l1=0; l1<m; ++l1) {
for(int r1=0; r1<m; ++r1) {
for(int i=0, j; i<d[l1][r1].size(); i=j+1) {
for(j=i; j+1<d[l1][r1].size()&&d[l1][r1][j+1]<=d[l1][r1][j]+1; ++j);
int l2=d[l1][r1][i], r2=d[l1][r1][j], x2=r2, y2=r1;
if(b)
swap(x2, y2);
for(int k=l2; k<=r2; ++k) {
int x=k, y=l1;
if(b)
swap(x, y);
p[x][y][b].push_back({-x2, y2});
}
}
d[l1][r1].clear();
}
}
}
long long count_rectangles(vector<vector<int>> a) {
n=a.size();
m=a[0].size();
vector<vector<int>> b(m, vector<int>(n));
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
b[j][i]=a[i][j];
gr(a, 0);
gr(b, 1);
// int s=0;
// for(int i=0; i<n; ++i)
// for(int j=0; j<m; ++j)
// s+=p[i][j][0].size()+p[i][j][1].size();
// if(s>12e6)
// return -1;
int ans=0;
for(int i=0; i<n; ++i) {
for(int j=0; j<m; ++j) {
for(int k : {0, 1})
sort(p[i][j][k].begin(), p[i][j][k].end());
int d=0;
for(int c=0; c<p[i][j][1].size(); ++c) {
while(d<p[i][j][0].size()&&p[i][j][0][d]<=p[i][j][1][c])
upd(p[i][j][0][d++][1], 1);
ans+=qry(p[i][j][1][c][1]+1);
}
while(d)
upd(p[i][j][0][--d][1], -1);
}
}
return ans;
}
Compilation message
rect.cpp: In function 'void gr(std::vector<std::vector<int> >, int)':
rect.cpp:43:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i=0, j; i<d[l1][r1].size(); i=j+1) {
| ~^~~~~~~~~~~~~~~~~
rect.cpp:44:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(j=i; j+1<d[l1][r1].size()&&d[l1][r1][j+1]<=d[l1][r1][j]+1; ++j);
| ~~~^~~~~~~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int c=0; c<p[i][j][1].size(); ++c) {
| ~^~~~~~~~~~~~~~~~~~
rect.cpp:82:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | while(d<p[i][j][0].size()&&p[i][j][0][d]<=p[i][j][1][c])
| ~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
300 ms |
440696 KB |
Output is correct |
2 |
Correct |
297 ms |
440696 KB |
Output is correct |
3 |
Correct |
293 ms |
440696 KB |
Output is correct |
4 |
Correct |
300 ms |
440696 KB |
Output is correct |
5 |
Correct |
303 ms |
440824 KB |
Output is correct |
6 |
Correct |
293 ms |
440696 KB |
Output is correct |
7 |
Correct |
298 ms |
440696 KB |
Output is correct |
8 |
Correct |
314 ms |
440620 KB |
Output is correct |
9 |
Correct |
308 ms |
440688 KB |
Output is correct |
10 |
Correct |
318 ms |
440696 KB |
Output is correct |
11 |
Correct |
295 ms |
440824 KB |
Output is correct |
12 |
Correct |
294 ms |
440696 KB |
Output is correct |
13 |
Correct |
297 ms |
440568 KB |
Output is correct |
14 |
Correct |
303 ms |
440572 KB |
Output is correct |
15 |
Correct |
299 ms |
440696 KB |
Output is correct |
16 |
Correct |
302 ms |
440568 KB |
Output is correct |
17 |
Correct |
300 ms |
440568 KB |
Output is correct |
18 |
Correct |
308 ms |
440568 KB |
Output is correct |
19 |
Correct |
296 ms |
440696 KB |
Output is correct |
20 |
Correct |
295 ms |
440664 KB |
Output is correct |
21 |
Correct |
297 ms |
440584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
300 ms |
440696 KB |
Output is correct |
2 |
Correct |
297 ms |
440696 KB |
Output is correct |
3 |
Correct |
293 ms |
440696 KB |
Output is correct |
4 |
Correct |
300 ms |
440696 KB |
Output is correct |
5 |
Correct |
303 ms |
440824 KB |
Output is correct |
6 |
Correct |
293 ms |
440696 KB |
Output is correct |
7 |
Correct |
298 ms |
440696 KB |
Output is correct |
8 |
Correct |
314 ms |
440620 KB |
Output is correct |
9 |
Correct |
308 ms |
440688 KB |
Output is correct |
10 |
Correct |
318 ms |
440696 KB |
Output is correct |
11 |
Correct |
295 ms |
440824 KB |
Output is correct |
12 |
Correct |
294 ms |
440696 KB |
Output is correct |
13 |
Correct |
297 ms |
440568 KB |
Output is correct |
14 |
Correct |
303 ms |
440572 KB |
Output is correct |
15 |
Correct |
299 ms |
440696 KB |
Output is correct |
16 |
Correct |
302 ms |
440568 KB |
Output is correct |
17 |
Correct |
298 ms |
441336 KB |
Output is correct |
18 |
Correct |
298 ms |
441208 KB |
Output is correct |
19 |
Correct |
300 ms |
441212 KB |
Output is correct |
20 |
Correct |
299 ms |
440952 KB |
Output is correct |
21 |
Correct |
301 ms |
441080 KB |
Output is correct |
22 |
Correct |
299 ms |
441080 KB |
Output is correct |
23 |
Correct |
311 ms |
441080 KB |
Output is correct |
24 |
Correct |
299 ms |
440824 KB |
Output is correct |
25 |
Correct |
300 ms |
440568 KB |
Output is correct |
26 |
Correct |
308 ms |
440568 KB |
Output is correct |
27 |
Correct |
296 ms |
440696 KB |
Output is correct |
28 |
Correct |
295 ms |
440664 KB |
Output is correct |
29 |
Correct |
297 ms |
440584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
300 ms |
440696 KB |
Output is correct |
2 |
Correct |
297 ms |
440696 KB |
Output is correct |
3 |
Correct |
293 ms |
440696 KB |
Output is correct |
4 |
Correct |
300 ms |
440696 KB |
Output is correct |
5 |
Correct |
303 ms |
440824 KB |
Output is correct |
6 |
Correct |
293 ms |
440696 KB |
Output is correct |
7 |
Correct |
298 ms |
440696 KB |
Output is correct |
8 |
Correct |
314 ms |
440620 KB |
Output is correct |
9 |
Correct |
308 ms |
440688 KB |
Output is correct |
10 |
Correct |
318 ms |
440696 KB |
Output is correct |
11 |
Correct |
295 ms |
440824 KB |
Output is correct |
12 |
Correct |
294 ms |
440696 KB |
Output is correct |
13 |
Correct |
297 ms |
440568 KB |
Output is correct |
14 |
Correct |
303 ms |
440572 KB |
Output is correct |
15 |
Correct |
299 ms |
440696 KB |
Output is correct |
16 |
Correct |
302 ms |
440568 KB |
Output is correct |
17 |
Correct |
298 ms |
441336 KB |
Output is correct |
18 |
Correct |
298 ms |
441208 KB |
Output is correct |
19 |
Correct |
300 ms |
441212 KB |
Output is correct |
20 |
Correct |
299 ms |
440952 KB |
Output is correct |
21 |
Correct |
301 ms |
441080 KB |
Output is correct |
22 |
Correct |
299 ms |
441080 KB |
Output is correct |
23 |
Correct |
311 ms |
441080 KB |
Output is correct |
24 |
Correct |
299 ms |
440824 KB |
Output is correct |
25 |
Correct |
309 ms |
444152 KB |
Output is correct |
26 |
Correct |
312 ms |
444152 KB |
Output is correct |
27 |
Correct |
307 ms |
444280 KB |
Output is correct |
28 |
Correct |
318 ms |
442488 KB |
Output is correct |
29 |
Correct |
318 ms |
443256 KB |
Output is correct |
30 |
Correct |
347 ms |
443384 KB |
Output is correct |
31 |
Correct |
314 ms |
443256 KB |
Output is correct |
32 |
Correct |
316 ms |
443256 KB |
Output is correct |
33 |
Correct |
300 ms |
440568 KB |
Output is correct |
34 |
Correct |
308 ms |
440568 KB |
Output is correct |
35 |
Correct |
296 ms |
440696 KB |
Output is correct |
36 |
Correct |
295 ms |
440664 KB |
Output is correct |
37 |
Correct |
297 ms |
440584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
300 ms |
440696 KB |
Output is correct |
2 |
Correct |
297 ms |
440696 KB |
Output is correct |
3 |
Correct |
293 ms |
440696 KB |
Output is correct |
4 |
Correct |
300 ms |
440696 KB |
Output is correct |
5 |
Correct |
303 ms |
440824 KB |
Output is correct |
6 |
Correct |
293 ms |
440696 KB |
Output is correct |
7 |
Correct |
298 ms |
440696 KB |
Output is correct |
8 |
Correct |
314 ms |
440620 KB |
Output is correct |
9 |
Correct |
308 ms |
440688 KB |
Output is correct |
10 |
Correct |
318 ms |
440696 KB |
Output is correct |
11 |
Correct |
295 ms |
440824 KB |
Output is correct |
12 |
Correct |
294 ms |
440696 KB |
Output is correct |
13 |
Correct |
297 ms |
440568 KB |
Output is correct |
14 |
Correct |
303 ms |
440572 KB |
Output is correct |
15 |
Correct |
299 ms |
440696 KB |
Output is correct |
16 |
Correct |
302 ms |
440568 KB |
Output is correct |
17 |
Correct |
298 ms |
441336 KB |
Output is correct |
18 |
Correct |
298 ms |
441208 KB |
Output is correct |
19 |
Correct |
300 ms |
441212 KB |
Output is correct |
20 |
Correct |
299 ms |
440952 KB |
Output is correct |
21 |
Correct |
301 ms |
441080 KB |
Output is correct |
22 |
Correct |
299 ms |
441080 KB |
Output is correct |
23 |
Correct |
311 ms |
441080 KB |
Output is correct |
24 |
Correct |
299 ms |
440824 KB |
Output is correct |
25 |
Correct |
309 ms |
444152 KB |
Output is correct |
26 |
Correct |
312 ms |
444152 KB |
Output is correct |
27 |
Correct |
307 ms |
444280 KB |
Output is correct |
28 |
Correct |
318 ms |
442488 KB |
Output is correct |
29 |
Correct |
318 ms |
443256 KB |
Output is correct |
30 |
Correct |
347 ms |
443384 KB |
Output is correct |
31 |
Correct |
314 ms |
443256 KB |
Output is correct |
32 |
Correct |
316 ms |
443256 KB |
Output is correct |
33 |
Correct |
439 ms |
472824 KB |
Output is correct |
34 |
Correct |
393 ms |
467960 KB |
Output is correct |
35 |
Correct |
415 ms |
468216 KB |
Output is correct |
36 |
Correct |
371 ms |
463224 KB |
Output is correct |
37 |
Correct |
453 ms |
483192 KB |
Output is correct |
38 |
Correct |
450 ms |
486060 KB |
Output is correct |
39 |
Correct |
469 ms |
483320 KB |
Output is correct |
40 |
Correct |
452 ms |
483320 KB |
Output is correct |
41 |
Correct |
404 ms |
458476 KB |
Output is correct |
42 |
Correct |
423 ms |
461560 KB |
Output is correct |
43 |
Correct |
540 ms |
470904 KB |
Output is correct |
44 |
Correct |
554 ms |
471812 KB |
Output is correct |
45 |
Correct |
422 ms |
456908 KB |
Output is correct |
46 |
Correct |
429 ms |
456952 KB |
Output is correct |
47 |
Correct |
525 ms |
470112 KB |
Output is correct |
48 |
Correct |
521 ms |
470264 KB |
Output is correct |
49 |
Correct |
300 ms |
440568 KB |
Output is correct |
50 |
Correct |
308 ms |
440568 KB |
Output is correct |
51 |
Correct |
296 ms |
440696 KB |
Output is correct |
52 |
Correct |
295 ms |
440664 KB |
Output is correct |
53 |
Correct |
297 ms |
440584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
325 ms |
441464 KB |
Output is correct |
2 |
Correct |
311 ms |
441336 KB |
Output is correct |
3 |
Correct |
318 ms |
441080 KB |
Output is correct |
4 |
Correct |
294 ms |
440568 KB |
Output is correct |
5 |
Correct |
318 ms |
441336 KB |
Output is correct |
6 |
Correct |
326 ms |
441384 KB |
Output is correct |
7 |
Correct |
324 ms |
441336 KB |
Output is correct |
8 |
Correct |
318 ms |
441336 KB |
Output is correct |
9 |
Correct |
321 ms |
441336 KB |
Output is correct |
10 |
Correct |
319 ms |
441208 KB |
Output is correct |
11 |
Correct |
319 ms |
441208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
300 ms |
440696 KB |
Output is correct |
2 |
Correct |
990 ms |
546032 KB |
Output is correct |
3 |
Correct |
1819 ms |
656868 KB |
Output is correct |
4 |
Correct |
1826 ms |
657912 KB |
Output is correct |
5 |
Correct |
1901 ms |
657784 KB |
Output is correct |
6 |
Correct |
473 ms |
490676 KB |
Output is correct |
7 |
Correct |
614 ms |
533816 KB |
Output is correct |
8 |
Correct |
626 ms |
540152 KB |
Output is correct |
9 |
Correct |
300 ms |
440568 KB |
Output is correct |
10 |
Correct |
308 ms |
440568 KB |
Output is correct |
11 |
Correct |
296 ms |
440696 KB |
Output is correct |
12 |
Correct |
295 ms |
440664 KB |
Output is correct |
13 |
Correct |
297 ms |
440584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
300 ms |
440696 KB |
Output is correct |
2 |
Correct |
297 ms |
440696 KB |
Output is correct |
3 |
Correct |
293 ms |
440696 KB |
Output is correct |
4 |
Correct |
300 ms |
440696 KB |
Output is correct |
5 |
Correct |
303 ms |
440824 KB |
Output is correct |
6 |
Correct |
293 ms |
440696 KB |
Output is correct |
7 |
Correct |
298 ms |
440696 KB |
Output is correct |
8 |
Correct |
314 ms |
440620 KB |
Output is correct |
9 |
Correct |
308 ms |
440688 KB |
Output is correct |
10 |
Correct |
318 ms |
440696 KB |
Output is correct |
11 |
Correct |
295 ms |
440824 KB |
Output is correct |
12 |
Correct |
294 ms |
440696 KB |
Output is correct |
13 |
Correct |
297 ms |
440568 KB |
Output is correct |
14 |
Correct |
303 ms |
440572 KB |
Output is correct |
15 |
Correct |
299 ms |
440696 KB |
Output is correct |
16 |
Correct |
302 ms |
440568 KB |
Output is correct |
17 |
Correct |
298 ms |
441336 KB |
Output is correct |
18 |
Correct |
298 ms |
441208 KB |
Output is correct |
19 |
Correct |
300 ms |
441212 KB |
Output is correct |
20 |
Correct |
299 ms |
440952 KB |
Output is correct |
21 |
Correct |
301 ms |
441080 KB |
Output is correct |
22 |
Correct |
299 ms |
441080 KB |
Output is correct |
23 |
Correct |
311 ms |
441080 KB |
Output is correct |
24 |
Correct |
299 ms |
440824 KB |
Output is correct |
25 |
Correct |
309 ms |
444152 KB |
Output is correct |
26 |
Correct |
312 ms |
444152 KB |
Output is correct |
27 |
Correct |
307 ms |
444280 KB |
Output is correct |
28 |
Correct |
318 ms |
442488 KB |
Output is correct |
29 |
Correct |
318 ms |
443256 KB |
Output is correct |
30 |
Correct |
347 ms |
443384 KB |
Output is correct |
31 |
Correct |
314 ms |
443256 KB |
Output is correct |
32 |
Correct |
316 ms |
443256 KB |
Output is correct |
33 |
Correct |
439 ms |
472824 KB |
Output is correct |
34 |
Correct |
393 ms |
467960 KB |
Output is correct |
35 |
Correct |
415 ms |
468216 KB |
Output is correct |
36 |
Correct |
371 ms |
463224 KB |
Output is correct |
37 |
Correct |
453 ms |
483192 KB |
Output is correct |
38 |
Correct |
450 ms |
486060 KB |
Output is correct |
39 |
Correct |
469 ms |
483320 KB |
Output is correct |
40 |
Correct |
452 ms |
483320 KB |
Output is correct |
41 |
Correct |
404 ms |
458476 KB |
Output is correct |
42 |
Correct |
423 ms |
461560 KB |
Output is correct |
43 |
Correct |
540 ms |
470904 KB |
Output is correct |
44 |
Correct |
554 ms |
471812 KB |
Output is correct |
45 |
Correct |
422 ms |
456908 KB |
Output is correct |
46 |
Correct |
429 ms |
456952 KB |
Output is correct |
47 |
Correct |
525 ms |
470112 KB |
Output is correct |
48 |
Correct |
521 ms |
470264 KB |
Output is correct |
49 |
Correct |
325 ms |
441464 KB |
Output is correct |
50 |
Correct |
311 ms |
441336 KB |
Output is correct |
51 |
Correct |
318 ms |
441080 KB |
Output is correct |
52 |
Correct |
294 ms |
440568 KB |
Output is correct |
53 |
Correct |
318 ms |
441336 KB |
Output is correct |
54 |
Correct |
326 ms |
441384 KB |
Output is correct |
55 |
Correct |
324 ms |
441336 KB |
Output is correct |
56 |
Correct |
318 ms |
441336 KB |
Output is correct |
57 |
Correct |
321 ms |
441336 KB |
Output is correct |
58 |
Correct |
319 ms |
441208 KB |
Output is correct |
59 |
Correct |
319 ms |
441208 KB |
Output is correct |
60 |
Correct |
300 ms |
440696 KB |
Output is correct |
61 |
Correct |
990 ms |
546032 KB |
Output is correct |
62 |
Correct |
1819 ms |
656868 KB |
Output is correct |
63 |
Correct |
1826 ms |
657912 KB |
Output is correct |
64 |
Correct |
1901 ms |
657784 KB |
Output is correct |
65 |
Correct |
473 ms |
490676 KB |
Output is correct |
66 |
Correct |
614 ms |
533816 KB |
Output is correct |
67 |
Correct |
626 ms |
540152 KB |
Output is correct |
68 |
Correct |
2659 ms |
834056 KB |
Output is correct |
69 |
Correct |
1660 ms |
766712 KB |
Output is correct |
70 |
Correct |
2688 ms |
766584 KB |
Output is correct |
71 |
Correct |
1344 ms |
699912 KB |
Output is correct |
72 |
Correct |
3562 ms |
968156 KB |
Output is correct |
73 |
Correct |
2483 ms |
685432 KB |
Output is correct |
74 |
Correct |
2659 ms |
687628 KB |
Output is correct |
75 |
Correct |
4062 ms |
813688 KB |
Output is correct |
76 |
Correct |
2601 ms |
675960 KB |
Output is correct |
77 |
Correct |
3343 ms |
748760 KB |
Output is correct |
78 |
Correct |
4122 ms |
819184 KB |
Output is correct |
79 |
Correct |
2263 ms |
662524 KB |
Output is correct |
80 |
Correct |
3700 ms |
803896 KB |
Output is correct |
81 |
Correct |
3613 ms |
793280 KB |
Output is correct |
82 |
Correct |
2241 ms |
778568 KB |
Output is correct |
83 |
Correct |
3537 ms |
970232 KB |
Output is correct |
84 |
Correct |
3570 ms |
970548 KB |
Output is correct |
85 |
Correct |
3543 ms |
970580 KB |
Output is correct |
86 |
Correct |
300 ms |
440568 KB |
Output is correct |
87 |
Correct |
308 ms |
440568 KB |
Output is correct |
88 |
Correct |
296 ms |
440696 KB |
Output is correct |
89 |
Correct |
295 ms |
440664 KB |
Output is correct |
90 |
Correct |
297 ms |
440584 KB |
Output is correct |