#include "rect.h"
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n, m;
struct DSU {
vector<int> p, sz;
vector<int> l, r;
vector<int> used;
int mx;
void reset(int s, int mm) {
p.assign(s + 3, -1);
sz.assign(s + 3, 0);
l.assign(s + 3, INF);
r.assign(s + 3, 0);
used.assign(s + 3, -1);
mx = mm;
}
void make_set(int x) {
p[x] = x;
sz[x] = 1;
l[x] = r[x] = x;
}
int find_set(int x) {
return p[x] == x ? x : find_set(p[x]);
}
void union_set(int x, int y) {
x = find_set(x); y = find_set(y);
if(x == y) return;
if(sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
p[y] = x;
l[x] = min(l[x], l[y]);
r[x] = max(r[x], r[y]);
}
bool check_val(int x) {
return !(l[x] == 0 || r[x] == mx);
}
};
long long count_rectangles(std::vector<std::vector<int> > a) {
n = (int)a.size();
m = (int)a[0].size();
vector<vector<array<int, 3 > > > row(n), col(m);
REP(i, n - 1) {
if(i == 0) continue;
DSU ds;
ds.reset(m, m - 1);
vector<int> ord;
REP(j, m) ord.pb(j);
sort(all(ord), [&](int x, int y) {
return a[i][x] < a[i][y];
});
int last = -1, lind = 0;
for(int k = 0; k < ord.size(); k++) {
auto &c = ord[k];
if(a[i][c] != last) {
for(int j = lind; j < k; j++) {
if(ds.used[ds.find_set(ord[j])] == lind) {
continue;
}
ds.used[ds.find_set(ord[j])] = lind;
if(!ds.check_val(ds.find_set(ord[j]))) continue;
row[i].pb({ds.l[ds.find_set(ord[j])], ds.r[ds.find_set(ord[j])]});
}
last = a[i][c];
lind = k;
}
ds.make_set(c);
if(ds.p[c + 1] != -1) ds.union_set(c, c + 1);
if(c > 0 && ds.p[c - 1] != -1) ds.union_set(c, c - 1);
}
for(int j = lind; j < ord.size(); j++) {
if(ds.used[ds.find_set(ord[j])] == lind) {
continue;
}
ds.used[ds.find_set(ord[j])] = lind;
if(!ds.check_val(ds.find_set(ord[j]))) continue;
row[i].pb({ds.l[ds.find_set(ord[j])], ds.r[ds.find_set(ord[j])], 0});
}
}
REP(j, m - 1) {
if(j == 0) continue;
DSU ds;
ds.reset(n, n - 1);
vector<int> ord;
REP(i, n) ord.pb(i);
sort(all(ord), [&](int x, int y) {
return a[x][j] < a[y][j];
});
int last = -1, lind = 0;
for(int k = 0; k < ord.size(); k++) {
auto &c = ord[k];
if(a[c][j] != last) {
for(int i = lind; i < k; i++) {
if(ds.used[ds.find_set(ord[i])] == lind) {
continue;
}
ds.used[ds.find_set(ord[i])] = lind;
if(!ds.check_val(ds.find_set(ord[i]))) continue;
col[j].pb({ds.l[ds.find_set(ord[i])], ds.r[ds.find_set(ord[i])]});
}
last = a[c][j];
lind = k;
}
ds.make_set(c);
if(ds.p[c + 1] != -1) ds.union_set(c, c + 1);
if(c > 0 && ds.p[c - 1] != -1) ds.union_set(c, c - 1);
}
for(int i = lind; i < ord.size(); i++) {
if(ds.used[ds.find_set(ord[i])] == lind) {
continue;
}
ds.used[ds.find_set(ord[i])] = lind;
if(!ds.check_val(ds.find_set(ord[i]))) continue;
col[j].pb({ds.l[ds.find_set(ord[i])], ds.r[ds.find_set(ord[i])], 0});
}
}
// cout << "rows: \n";
// for(int i = 0; i < n; i++) {
// cout << "i:" << i << "\n";
// for(auto c : row[i]) {
// cout << c[0] << " " << c[1] << "\n";
// }
// }
map<array<int, 3>, int > mpp;
for(int i = n - 1; i >= 0; i--) {
for(auto &c : row[i]) {
mpp[{i, c[0], c[1]}] = c[2] = mpp[{i + 1, c[0], c[1]}] + 1;
}
}
mpp.clear();
for(int i = m - 1; i >= 0; i--) {
for(auto &c : col[i]) {
mpp[{i, c[0], c[1]}] = c[2] = mpp[{i + 1, c[0], c[1]}] + 1;
}
}
int ans = 0;
for(int i = 0; i < n; i++) {
for(auto &c : row[i]) {
for(auto cl : col[c[0]]) {
if(cl[0] != i) continue;
if(cl[1] - cl[0] + 1 <= c[2] && c[1] - c[0] + 1 <= cl[2]) {
ans++;
}
}
}
}
return ans;
}
// int main() {
// int n, m;
// cin >> n >> m;
// vector<vector<int> > grid(n,vector<int>(m));
// REP(i, n) REP(j, m) {
// cin >> grid[i][j];
// }
// cout << count_rectangles(grid) << "\n";
// return 0;
// }
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int k = 0; k < ord.size(); k++) {
| ~~~^~~~~~~~~~~~
rect.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int j = lind; j < ord.size(); j++) {
| ~~^~~~~~~~~~~~
rect.cpp:118:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(int k = 0; k < ord.size(); k++) {
| ~~^~~~~~~~~~~~
rect.cpp:137:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(int i = lind; i < ord.size(); i++) {
| ~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
4 ms |
1112 KB |
Output is correct |
23 |
Correct |
3 ms |
1016 KB |
Output is correct |
24 |
Correct |
4 ms |
1116 KB |
Output is correct |
25 |
Correct |
2 ms |
604 KB |
Output is correct |
26 |
Correct |
5 ms |
1376 KB |
Output is correct |
27 |
Correct |
4 ms |
1372 KB |
Output is correct |
28 |
Correct |
4 ms |
1116 KB |
Output is correct |
29 |
Correct |
3 ms |
608 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
4 ms |
1112 KB |
Output is correct |
18 |
Correct |
3 ms |
1016 KB |
Output is correct |
19 |
Correct |
4 ms |
1116 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
21 |
Correct |
5 ms |
1376 KB |
Output is correct |
22 |
Correct |
4 ms |
1372 KB |
Output is correct |
23 |
Correct |
4 ms |
1116 KB |
Output is correct |
24 |
Correct |
3 ms |
608 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
27 ms |
4444 KB |
Output is correct |
31 |
Correct |
27 ms |
4444 KB |
Output is correct |
32 |
Correct |
27 ms |
4700 KB |
Output is correct |
33 |
Correct |
13 ms |
3164 KB |
Output is correct |
34 |
Correct |
33 ms |
6360 KB |
Output is correct |
35 |
Correct |
32 ms |
6492 KB |
Output is correct |
36 |
Correct |
30 ms |
5720 KB |
Output is correct |
37 |
Correct |
28 ms |
5896 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
4 ms |
1112 KB |
Output is correct |
18 |
Correct |
3 ms |
1016 KB |
Output is correct |
19 |
Correct |
4 ms |
1116 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
21 |
Correct |
5 ms |
1376 KB |
Output is correct |
22 |
Correct |
4 ms |
1372 KB |
Output is correct |
23 |
Correct |
4 ms |
1116 KB |
Output is correct |
24 |
Correct |
3 ms |
608 KB |
Output is correct |
25 |
Correct |
27 ms |
4444 KB |
Output is correct |
26 |
Correct |
27 ms |
4444 KB |
Output is correct |
27 |
Correct |
27 ms |
4700 KB |
Output is correct |
28 |
Correct |
13 ms |
3164 KB |
Output is correct |
29 |
Correct |
33 ms |
6360 KB |
Output is correct |
30 |
Correct |
32 ms |
6492 KB |
Output is correct |
31 |
Correct |
30 ms |
5720 KB |
Output is correct |
32 |
Correct |
28 ms |
5896 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
225 ms |
46164 KB |
Output is correct |
39 |
Correct |
249 ms |
45864 KB |
Output is correct |
40 |
Correct |
244 ms |
46420 KB |
Output is correct |
41 |
Correct |
260 ms |
46164 KB |
Output is correct |
42 |
Correct |
551 ms |
54868 KB |
Output is correct |
43 |
Correct |
552 ms |
54864 KB |
Output is correct |
44 |
Correct |
563 ms |
55120 KB |
Output is correct |
45 |
Correct |
507 ms |
52080 KB |
Output is correct |
46 |
Correct |
122 ms |
24144 KB |
Output is correct |
47 |
Correct |
203 ms |
35664 KB |
Output is correct |
48 |
Correct |
687 ms |
77136 KB |
Output is correct |
49 |
Correct |
692 ms |
79784 KB |
Output is correct |
50 |
Correct |
317 ms |
39912 KB |
Output is correct |
51 |
Correct |
273 ms |
39996 KB |
Output is correct |
52 |
Correct |
601 ms |
68872 KB |
Output is correct |
53 |
Correct |
603 ms |
69908 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
860 KB |
Output is correct |
2 |
Correct |
2 ms |
780 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
388 KB |
Output is correct |
5 |
Correct |
2 ms |
860 KB |
Output is correct |
6 |
Correct |
2 ms |
860 KB |
Output is correct |
7 |
Correct |
2 ms |
860 KB |
Output is correct |
8 |
Correct |
2 ms |
860 KB |
Output is correct |
9 |
Correct |
2 ms |
700 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
959 ms |
141700 KB |
Output is correct |
8 |
Correct |
2420 ms |
303996 KB |
Output is correct |
9 |
Correct |
2460 ms |
305420 KB |
Output is correct |
10 |
Correct |
2384 ms |
305276 KB |
Output is correct |
11 |
Correct |
150 ms |
30708 KB |
Output is correct |
12 |
Correct |
331 ms |
57992 KB |
Output is correct |
13 |
Correct |
358 ms |
61776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
4 ms |
1112 KB |
Output is correct |
18 |
Correct |
3 ms |
1016 KB |
Output is correct |
19 |
Correct |
4 ms |
1116 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
21 |
Correct |
5 ms |
1376 KB |
Output is correct |
22 |
Correct |
4 ms |
1372 KB |
Output is correct |
23 |
Correct |
4 ms |
1116 KB |
Output is correct |
24 |
Correct |
3 ms |
608 KB |
Output is correct |
25 |
Correct |
27 ms |
4444 KB |
Output is correct |
26 |
Correct |
27 ms |
4444 KB |
Output is correct |
27 |
Correct |
27 ms |
4700 KB |
Output is correct |
28 |
Correct |
13 ms |
3164 KB |
Output is correct |
29 |
Correct |
33 ms |
6360 KB |
Output is correct |
30 |
Correct |
32 ms |
6492 KB |
Output is correct |
31 |
Correct |
30 ms |
5720 KB |
Output is correct |
32 |
Correct |
28 ms |
5896 KB |
Output is correct |
33 |
Correct |
225 ms |
46164 KB |
Output is correct |
34 |
Correct |
249 ms |
45864 KB |
Output is correct |
35 |
Correct |
244 ms |
46420 KB |
Output is correct |
36 |
Correct |
260 ms |
46164 KB |
Output is correct |
37 |
Correct |
551 ms |
54868 KB |
Output is correct |
38 |
Correct |
552 ms |
54864 KB |
Output is correct |
39 |
Correct |
563 ms |
55120 KB |
Output is correct |
40 |
Correct |
507 ms |
52080 KB |
Output is correct |
41 |
Correct |
122 ms |
24144 KB |
Output is correct |
42 |
Correct |
203 ms |
35664 KB |
Output is correct |
43 |
Correct |
687 ms |
77136 KB |
Output is correct |
44 |
Correct |
692 ms |
79784 KB |
Output is correct |
45 |
Correct |
317 ms |
39912 KB |
Output is correct |
46 |
Correct |
273 ms |
39996 KB |
Output is correct |
47 |
Correct |
601 ms |
68872 KB |
Output is correct |
48 |
Correct |
603 ms |
69908 KB |
Output is correct |
49 |
Correct |
2 ms |
860 KB |
Output is correct |
50 |
Correct |
2 ms |
780 KB |
Output is correct |
51 |
Correct |
1 ms |
604 KB |
Output is correct |
52 |
Correct |
0 ms |
388 KB |
Output is correct |
53 |
Correct |
2 ms |
860 KB |
Output is correct |
54 |
Correct |
2 ms |
860 KB |
Output is correct |
55 |
Correct |
2 ms |
860 KB |
Output is correct |
56 |
Correct |
2 ms |
860 KB |
Output is correct |
57 |
Correct |
2 ms |
700 KB |
Output is correct |
58 |
Correct |
0 ms |
348 KB |
Output is correct |
59 |
Correct |
1 ms |
348 KB |
Output is correct |
60 |
Correct |
0 ms |
348 KB |
Output is correct |
61 |
Correct |
959 ms |
141700 KB |
Output is correct |
62 |
Correct |
2420 ms |
303996 KB |
Output is correct |
63 |
Correct |
2460 ms |
305420 KB |
Output is correct |
64 |
Correct |
2384 ms |
305276 KB |
Output is correct |
65 |
Correct |
150 ms |
30708 KB |
Output is correct |
66 |
Correct |
331 ms |
57992 KB |
Output is correct |
67 |
Correct |
358 ms |
61776 KB |
Output is correct |
68 |
Correct |
0 ms |
348 KB |
Output is correct |
69 |
Correct |
0 ms |
348 KB |
Output is correct |
70 |
Correct |
0 ms |
348 KB |
Output is correct |
71 |
Correct |
0 ms |
348 KB |
Output is correct |
72 |
Correct |
0 ms |
348 KB |
Output is correct |
73 |
Correct |
4841 ms |
574624 KB |
Output is correct |
74 |
Execution timed out |
5074 ms |
574716 KB |
Time limit exceeded |
75 |
Halted |
0 ms |
0 KB |
- |