// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2")
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2505;
const int inf = 1e9;
typedef pair<int, int> pii;
typedef pair<pii, pii> rect;
int prv[2][MAXN][MAXN];
int nxt[2][MAXN][MAXN];
int n, m;
void make(int store[][MAXN], bool rc, bool dir, vector<vector<int>> &a, int v) {
vector<pii> stck;
stck.push_back(pii(inf, -1));
int sz = (rc ? n : m);
for (int i = (dir ? sz-1 : 0); (dir ? i >= 0 : i < sz); (dir ? i-- : i++)) {
int cur = (rc) ? a[i][v] : a[v][i];
while (cur >= stck.back().first) stck.pop_back();
if (rc) store[i][v] = stck.back().second;
else store[v][i] = stck.back().second;
stck.push_back(pii(cur, i));
}
}
vector<int> occ[2][MAXN][MAXN];
int cnt_leq(vector<int> &v, int i) {
int mn = -1;
int mx = v.size();
while (mx > mn+1) {
int cur = (mn+mx)/2;
if (v[cur] <= i) mn = cur;
else mx = cur;
}
return mx;
}
void print(rect &r) {
cout << r.first.first << ' ' << r.first.second << ' ' << r.second.first << ' ' << r.second.second << '\n';
}
vector<rect> cands;
long long count_rectangles(vector<vector<int>> a) {
n = a.size();
m = a[0].size();
for (int i = 0; i < n; i++) {
make(prv[0], 0, 0, a, i);
make(nxt[0], 0, 1, a, i);
}
for (int i = 0; i < m; i++) {
make(prv[1], 1, 0, a, i);
make(nxt[1], 1, 1, a, i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int suc = 0;
for (int t = 0; t < 2; t++) {
int rcpos = (t ? i : j);
if (nxt[t][i][j] != -1 && prv[t][i][j] != -1) {
suc++;
if (nxt[t][i][j]) {
occ[t][prv[t][i][j]+1][nxt[t][i][j]-1].push_back(i^j^rcpos);
}
}
}
if (suc == 2) {
// cerr << i << ' ' << j << '\n';
cands.push_back(rect(pii(prv[1][i][j]+1, prv[0][i][j]+1), pii(nxt[1][i][j]-1, nxt[0][i][j]-1)));
}
}
}
for (int u = 1; u < m-1; u++) {
for (int v = u; v < m-1; v++) {
sort(occ[0][u][v].begin(), occ[0][u][v].end());
int p = 0;
int pv = -1;
for (int i = 0; i < occ[0][u][v].size(); i++) {
if (occ[0][u][v][i] == pv) continue;
pv = occ[0][u][v][i];
swap(occ[0][u][v][p++], occ[0][u][v][i]);
}
occ[0][u][v].resize(p);
}
}
for (int u = 1; u < n-1; u++) {
for (int v = u; v < n-1; v++) {
sort(occ[1][u][v].begin(), occ[1][u][v].end());
int p = 0;
int pv = -1;
for (int i = 0; i < occ[1][u][v].size(); i++) {
if (occ[1][u][v][i] == pv) continue;
pv = occ[1][u][v][i];
swap(occ[1][u][v][p++], occ[1][u][v][i]);
}
occ[1][u][v].resize(p);
}
}
int ans = 0;
// cerr << cands.size() << '\n';
sort(cands.begin(), cands.end());
int p = 0;
rect pv(pii(-1, -1), pii(-1, -1));
for (int i = 0; i < cands.size(); i++) {
if (cands[i] == pv) continue;
pv = cands[i];
swap(cands[p++], cands[i]);
}
cands.resize(p);
for (rect r: cands) {
// print(r);
pii up = r.first;
pii down = r.second;
pii xrange = pii(up.first, down.first);
pii yrange = pii(up.second, down.second);
if ((cnt_leq(occ[0][yrange.first][yrange.second], xrange.second)-cnt_leq(occ[0][yrange.first][yrange.second], xrange.first-1) == xrange.second-xrange.first+1)
&& (cnt_leq(occ[1][xrange.first][xrange.second], yrange.second)-cnt_leq(occ[1][xrange.first][xrange.second], yrange.first-1) == yrange.second-yrange.first+1)) {
// cerr << xrange.second-xrange.first+1 << ' ' << cnt_leq(occ[0][yrange], xrange.second)
// << ' ' << cnt_leq(occ[0][yrange], xrange.first-1) << '\n';
// print(r);
ans++;
}
}
return ans;
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int i = 0; i < occ[0][u][v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (int i = 0; i < occ[1][u][v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:112:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for (int i = 0; i < cands.size(); i++) {
| ~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
295076 KB |
Output is correct |
2 |
Correct |
121 ms |
295436 KB |
Output is correct |
3 |
Correct |
127 ms |
295500 KB |
Output is correct |
4 |
Correct |
119 ms |
295516 KB |
Output is correct |
5 |
Correct |
118 ms |
295480 KB |
Output is correct |
6 |
Correct |
120 ms |
295524 KB |
Output is correct |
7 |
Correct |
125 ms |
295492 KB |
Output is correct |
8 |
Correct |
119 ms |
295176 KB |
Output is correct |
9 |
Correct |
122 ms |
295492 KB |
Output is correct |
10 |
Correct |
122 ms |
295524 KB |
Output is correct |
11 |
Correct |
121 ms |
295508 KB |
Output is correct |
12 |
Correct |
121 ms |
295460 KB |
Output is correct |
13 |
Correct |
118 ms |
294960 KB |
Output is correct |
14 |
Correct |
118 ms |
295048 KB |
Output is correct |
15 |
Correct |
120 ms |
295048 KB |
Output is correct |
16 |
Correct |
120 ms |
294988 KB |
Output is correct |
17 |
Correct |
126 ms |
294996 KB |
Output is correct |
18 |
Correct |
128 ms |
294956 KB |
Output is correct |
19 |
Correct |
122 ms |
295528 KB |
Output is correct |
20 |
Correct |
122 ms |
295396 KB |
Output is correct |
21 |
Correct |
121 ms |
295164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
295076 KB |
Output is correct |
2 |
Correct |
121 ms |
295436 KB |
Output is correct |
3 |
Correct |
127 ms |
295500 KB |
Output is correct |
4 |
Correct |
119 ms |
295516 KB |
Output is correct |
5 |
Correct |
118 ms |
295480 KB |
Output is correct |
6 |
Correct |
120 ms |
295524 KB |
Output is correct |
7 |
Correct |
125 ms |
295492 KB |
Output is correct |
8 |
Correct |
119 ms |
295176 KB |
Output is correct |
9 |
Correct |
122 ms |
295492 KB |
Output is correct |
10 |
Correct |
122 ms |
295524 KB |
Output is correct |
11 |
Correct |
121 ms |
295508 KB |
Output is correct |
12 |
Correct |
121 ms |
295460 KB |
Output is correct |
13 |
Correct |
118 ms |
294960 KB |
Output is correct |
14 |
Correct |
118 ms |
295048 KB |
Output is correct |
15 |
Correct |
120 ms |
295048 KB |
Output is correct |
16 |
Correct |
120 ms |
294988 KB |
Output is correct |
17 |
Correct |
126 ms |
294996 KB |
Output is correct |
18 |
Correct |
128 ms |
294956 KB |
Output is correct |
19 |
Correct |
122 ms |
295528 KB |
Output is correct |
20 |
Correct |
122 ms |
295396 KB |
Output is correct |
21 |
Correct |
121 ms |
295164 KB |
Output is correct |
22 |
Correct |
121 ms |
296600 KB |
Output is correct |
23 |
Correct |
121 ms |
296620 KB |
Output is correct |
24 |
Correct |
121 ms |
296652 KB |
Output is correct |
25 |
Correct |
122 ms |
296524 KB |
Output is correct |
26 |
Correct |
123 ms |
296616 KB |
Output is correct |
27 |
Correct |
127 ms |
296656 KB |
Output is correct |
28 |
Correct |
125 ms |
296624 KB |
Output is correct |
29 |
Correct |
122 ms |
296396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
295076 KB |
Output is correct |
2 |
Correct |
121 ms |
295436 KB |
Output is correct |
3 |
Correct |
127 ms |
295500 KB |
Output is correct |
4 |
Correct |
119 ms |
295516 KB |
Output is correct |
5 |
Correct |
118 ms |
295480 KB |
Output is correct |
6 |
Correct |
120 ms |
295524 KB |
Output is correct |
7 |
Correct |
125 ms |
295492 KB |
Output is correct |
8 |
Correct |
119 ms |
295176 KB |
Output is correct |
9 |
Correct |
122 ms |
295492 KB |
Output is correct |
10 |
Correct |
122 ms |
295524 KB |
Output is correct |
11 |
Correct |
121 ms |
295508 KB |
Output is correct |
12 |
Correct |
121 ms |
295460 KB |
Output is correct |
13 |
Correct |
118 ms |
294960 KB |
Output is correct |
14 |
Correct |
118 ms |
295048 KB |
Output is correct |
15 |
Correct |
120 ms |
295048 KB |
Output is correct |
16 |
Correct |
120 ms |
294988 KB |
Output is correct |
17 |
Correct |
121 ms |
296600 KB |
Output is correct |
18 |
Correct |
121 ms |
296620 KB |
Output is correct |
19 |
Correct |
121 ms |
296652 KB |
Output is correct |
20 |
Correct |
122 ms |
296524 KB |
Output is correct |
21 |
Correct |
123 ms |
296616 KB |
Output is correct |
22 |
Correct |
127 ms |
296656 KB |
Output is correct |
23 |
Correct |
125 ms |
296624 KB |
Output is correct |
24 |
Correct |
122 ms |
296396 KB |
Output is correct |
25 |
Correct |
126 ms |
294996 KB |
Output is correct |
26 |
Correct |
128 ms |
294956 KB |
Output is correct |
27 |
Correct |
122 ms |
295528 KB |
Output is correct |
28 |
Correct |
122 ms |
295396 KB |
Output is correct |
29 |
Correct |
121 ms |
295164 KB |
Output is correct |
30 |
Correct |
128 ms |
300604 KB |
Output is correct |
31 |
Correct |
130 ms |
300712 KB |
Output is correct |
32 |
Correct |
131 ms |
300664 KB |
Output is correct |
33 |
Correct |
130 ms |
299972 KB |
Output is correct |
34 |
Correct |
135 ms |
300868 KB |
Output is correct |
35 |
Correct |
138 ms |
300880 KB |
Output is correct |
36 |
Correct |
135 ms |
300736 KB |
Output is correct |
37 |
Correct |
136 ms |
300796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
295076 KB |
Output is correct |
2 |
Correct |
121 ms |
295436 KB |
Output is correct |
3 |
Correct |
127 ms |
295500 KB |
Output is correct |
4 |
Correct |
119 ms |
295516 KB |
Output is correct |
5 |
Correct |
118 ms |
295480 KB |
Output is correct |
6 |
Correct |
120 ms |
295524 KB |
Output is correct |
7 |
Correct |
125 ms |
295492 KB |
Output is correct |
8 |
Correct |
119 ms |
295176 KB |
Output is correct |
9 |
Correct |
122 ms |
295492 KB |
Output is correct |
10 |
Correct |
122 ms |
295524 KB |
Output is correct |
11 |
Correct |
121 ms |
295508 KB |
Output is correct |
12 |
Correct |
121 ms |
295460 KB |
Output is correct |
13 |
Correct |
118 ms |
294960 KB |
Output is correct |
14 |
Correct |
118 ms |
295048 KB |
Output is correct |
15 |
Correct |
120 ms |
295048 KB |
Output is correct |
16 |
Correct |
120 ms |
294988 KB |
Output is correct |
17 |
Correct |
121 ms |
296600 KB |
Output is correct |
18 |
Correct |
121 ms |
296620 KB |
Output is correct |
19 |
Correct |
121 ms |
296652 KB |
Output is correct |
20 |
Correct |
122 ms |
296524 KB |
Output is correct |
21 |
Correct |
123 ms |
296616 KB |
Output is correct |
22 |
Correct |
127 ms |
296656 KB |
Output is correct |
23 |
Correct |
125 ms |
296624 KB |
Output is correct |
24 |
Correct |
122 ms |
296396 KB |
Output is correct |
25 |
Correct |
128 ms |
300604 KB |
Output is correct |
26 |
Correct |
130 ms |
300712 KB |
Output is correct |
27 |
Correct |
131 ms |
300664 KB |
Output is correct |
28 |
Correct |
130 ms |
299972 KB |
Output is correct |
29 |
Correct |
135 ms |
300868 KB |
Output is correct |
30 |
Correct |
138 ms |
300880 KB |
Output is correct |
31 |
Correct |
135 ms |
300736 KB |
Output is correct |
32 |
Correct |
136 ms |
300796 KB |
Output is correct |
33 |
Correct |
126 ms |
294996 KB |
Output is correct |
34 |
Correct |
128 ms |
294956 KB |
Output is correct |
35 |
Correct |
122 ms |
295528 KB |
Output is correct |
36 |
Correct |
122 ms |
295396 KB |
Output is correct |
37 |
Correct |
121 ms |
295164 KB |
Output is correct |
38 |
Correct |
187 ms |
333132 KB |
Output is correct |
39 |
Correct |
187 ms |
333156 KB |
Output is correct |
40 |
Correct |
190 ms |
333100 KB |
Output is correct |
41 |
Correct |
186 ms |
333124 KB |
Output is correct |
42 |
Correct |
245 ms |
331252 KB |
Output is correct |
43 |
Correct |
237 ms |
331228 KB |
Output is correct |
44 |
Correct |
240 ms |
331256 KB |
Output is correct |
45 |
Correct |
247 ms |
329128 KB |
Output is correct |
46 |
Correct |
209 ms |
324656 KB |
Output is correct |
47 |
Correct |
239 ms |
329208 KB |
Output is correct |
48 |
Correct |
316 ms |
331752 KB |
Output is correct |
49 |
Correct |
312 ms |
331864 KB |
Output is correct |
50 |
Correct |
211 ms |
319252 KB |
Output is correct |
51 |
Correct |
218 ms |
313600 KB |
Output is correct |
52 |
Correct |
297 ms |
331012 KB |
Output is correct |
53 |
Correct |
303 ms |
330984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
133 ms |
295456 KB |
Output is correct |
2 |
Correct |
133 ms |
295364 KB |
Output is correct |
3 |
Correct |
131 ms |
295136 KB |
Output is correct |
4 |
Correct |
127 ms |
294988 KB |
Output is correct |
5 |
Correct |
133 ms |
295440 KB |
Output is correct |
6 |
Correct |
134 ms |
295448 KB |
Output is correct |
7 |
Correct |
133 ms |
295456 KB |
Output is correct |
8 |
Correct |
133 ms |
295428 KB |
Output is correct |
9 |
Correct |
141 ms |
295536 KB |
Output is correct |
10 |
Correct |
134 ms |
295096 KB |
Output is correct |
11 |
Correct |
134 ms |
295316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
126 ms |
294996 KB |
Output is correct |
2 |
Correct |
128 ms |
294956 KB |
Output is correct |
3 |
Correct |
122 ms |
295528 KB |
Output is correct |
4 |
Correct |
122 ms |
295396 KB |
Output is correct |
5 |
Correct |
121 ms |
295164 KB |
Output is correct |
6 |
Correct |
125 ms |
295068 KB |
Output is correct |
7 |
Correct |
693 ms |
411716 KB |
Output is correct |
8 |
Correct |
1417 ms |
532116 KB |
Output is correct |
9 |
Correct |
1432 ms |
533088 KB |
Output is correct |
10 |
Correct |
1426 ms |
532976 KB |
Output is correct |
11 |
Correct |
323 ms |
367728 KB |
Output is correct |
12 |
Correct |
502 ms |
439268 KB |
Output is correct |
13 |
Correct |
530 ms |
442304 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
295076 KB |
Output is correct |
2 |
Correct |
121 ms |
295436 KB |
Output is correct |
3 |
Correct |
127 ms |
295500 KB |
Output is correct |
4 |
Correct |
119 ms |
295516 KB |
Output is correct |
5 |
Correct |
118 ms |
295480 KB |
Output is correct |
6 |
Correct |
120 ms |
295524 KB |
Output is correct |
7 |
Correct |
125 ms |
295492 KB |
Output is correct |
8 |
Correct |
119 ms |
295176 KB |
Output is correct |
9 |
Correct |
122 ms |
295492 KB |
Output is correct |
10 |
Correct |
122 ms |
295524 KB |
Output is correct |
11 |
Correct |
121 ms |
295508 KB |
Output is correct |
12 |
Correct |
121 ms |
295460 KB |
Output is correct |
13 |
Correct |
118 ms |
294960 KB |
Output is correct |
14 |
Correct |
118 ms |
295048 KB |
Output is correct |
15 |
Correct |
120 ms |
295048 KB |
Output is correct |
16 |
Correct |
120 ms |
294988 KB |
Output is correct |
17 |
Correct |
121 ms |
296600 KB |
Output is correct |
18 |
Correct |
121 ms |
296620 KB |
Output is correct |
19 |
Correct |
121 ms |
296652 KB |
Output is correct |
20 |
Correct |
122 ms |
296524 KB |
Output is correct |
21 |
Correct |
123 ms |
296616 KB |
Output is correct |
22 |
Correct |
127 ms |
296656 KB |
Output is correct |
23 |
Correct |
125 ms |
296624 KB |
Output is correct |
24 |
Correct |
122 ms |
296396 KB |
Output is correct |
25 |
Correct |
128 ms |
300604 KB |
Output is correct |
26 |
Correct |
130 ms |
300712 KB |
Output is correct |
27 |
Correct |
131 ms |
300664 KB |
Output is correct |
28 |
Correct |
130 ms |
299972 KB |
Output is correct |
29 |
Correct |
135 ms |
300868 KB |
Output is correct |
30 |
Correct |
138 ms |
300880 KB |
Output is correct |
31 |
Correct |
135 ms |
300736 KB |
Output is correct |
32 |
Correct |
136 ms |
300796 KB |
Output is correct |
33 |
Correct |
187 ms |
333132 KB |
Output is correct |
34 |
Correct |
187 ms |
333156 KB |
Output is correct |
35 |
Correct |
190 ms |
333100 KB |
Output is correct |
36 |
Correct |
186 ms |
333124 KB |
Output is correct |
37 |
Correct |
245 ms |
331252 KB |
Output is correct |
38 |
Correct |
237 ms |
331228 KB |
Output is correct |
39 |
Correct |
240 ms |
331256 KB |
Output is correct |
40 |
Correct |
247 ms |
329128 KB |
Output is correct |
41 |
Correct |
209 ms |
324656 KB |
Output is correct |
42 |
Correct |
239 ms |
329208 KB |
Output is correct |
43 |
Correct |
316 ms |
331752 KB |
Output is correct |
44 |
Correct |
312 ms |
331864 KB |
Output is correct |
45 |
Correct |
211 ms |
319252 KB |
Output is correct |
46 |
Correct |
218 ms |
313600 KB |
Output is correct |
47 |
Correct |
297 ms |
331012 KB |
Output is correct |
48 |
Correct |
303 ms |
330984 KB |
Output is correct |
49 |
Correct |
133 ms |
295456 KB |
Output is correct |
50 |
Correct |
133 ms |
295364 KB |
Output is correct |
51 |
Correct |
131 ms |
295136 KB |
Output is correct |
52 |
Correct |
127 ms |
294988 KB |
Output is correct |
53 |
Correct |
133 ms |
295440 KB |
Output is correct |
54 |
Correct |
134 ms |
295448 KB |
Output is correct |
55 |
Correct |
133 ms |
295456 KB |
Output is correct |
56 |
Correct |
133 ms |
295428 KB |
Output is correct |
57 |
Correct |
141 ms |
295536 KB |
Output is correct |
58 |
Correct |
134 ms |
295096 KB |
Output is correct |
59 |
Correct |
134 ms |
295316 KB |
Output is correct |
60 |
Correct |
125 ms |
295068 KB |
Output is correct |
61 |
Correct |
693 ms |
411716 KB |
Output is correct |
62 |
Correct |
1417 ms |
532116 KB |
Output is correct |
63 |
Correct |
1432 ms |
533088 KB |
Output is correct |
64 |
Correct |
1426 ms |
532976 KB |
Output is correct |
65 |
Correct |
323 ms |
367728 KB |
Output is correct |
66 |
Correct |
502 ms |
439268 KB |
Output is correct |
67 |
Correct |
530 ms |
442304 KB |
Output is correct |
68 |
Correct |
126 ms |
294996 KB |
Output is correct |
69 |
Correct |
128 ms |
294956 KB |
Output is correct |
70 |
Correct |
122 ms |
295528 KB |
Output is correct |
71 |
Correct |
122 ms |
295396 KB |
Output is correct |
72 |
Correct |
121 ms |
295164 KB |
Output is correct |
73 |
Correct |
1246 ms |
637836 KB |
Output is correct |
74 |
Correct |
915 ms |
637700 KB |
Output is correct |
75 |
Correct |
1435 ms |
637704 KB |
Output is correct |
76 |
Correct |
1145 ms |
637756 KB |
Output is correct |
77 |
Correct |
2205 ms |
616808 KB |
Output is correct |
78 |
Correct |
1877 ms |
487392 KB |
Output is correct |
79 |
Correct |
1994 ms |
537460 KB |
Output is correct |
80 |
Correct |
3183 ms |
629580 KB |
Output is correct |
81 |
Correct |
1975 ms |
495812 KB |
Output is correct |
82 |
Correct |
2619 ms |
630300 KB |
Output is correct |
83 |
Correct |
3322 ms |
645252 KB |
Output is correct |
84 |
Correct |
1719 ms |
504776 KB |
Output is correct |
85 |
Correct |
3025 ms |
639276 KB |
Output is correct |
86 |
Correct |
3010 ms |
634768 KB |
Output is correct |
87 |
Correct |
1502 ms |
530928 KB |
Output is correct |
88 |
Correct |
2259 ms |
630792 KB |
Output is correct |
89 |
Correct |
2246 ms |
631096 KB |
Output is correct |
90 |
Correct |
2164 ms |
631064 KB |
Output is correct |