# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
820869 |
2023-08-11T06:20:31 Z |
resting |
Rectangles (IOI19_rect) |
C++17 |
|
3796 ms |
782000 KB |
//#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu {
vector<int> p, s, l, r;
dsu(int n) : p(n, -1), s(n, 0), l(n), r(n) { for (int i = 0; i < n; i++) l[i] = r[i] = i; };
dsu() :dsu(0) {};
int getp(int v) {
return p[v] == -1 ? v : p[v] = getp(p[v]);
}
void merge(int a, int b) {
a = getp(a); b = getp(b);
if (a == b) return;
if (s[a] < s[b]) swap(a, b);
if (s[a] == s[b]) s[a]++;
l[a] = min(l[a], l[b]);
r[a] = max(r[a], r[b]);
p[b] = a;
}
};
const int mx = 2505;
//binary index tree
struct bit {
vector<int> b; int n;
bit(int n) : n(n), b(n, 0) {}
void upd(int i, int v) { for (i++; i <= n; i += i & -i) b[i - 1] += v; }
void upd(int l, int r, int v) { upd(l, v); upd(r + 1, -v); }
int q(int i) { int v = 0; for (i++; i > 0; i -= i & -i) v += b[i - 1];return v; }
int q(int l, int r) { return q(r) - q(l - 1); }
} uwu(mx);
long long count_rectangles(vector<vector<int32_t>> a) {
int n = a.size(), m = a[0].size();
vector<vector<vector<pair<short, short>>>> vert, hori; // idfc
vert = hori = vector<vector<vector<pair<short, short>>>>(n, vector<vector<pair<short, short>>>(m));
for (int i = 0; i < n; i++) {
vector<pair<int, int>> v;
vector<int> vis(mx, 0);
for (int j = 0; j < m; j++) v.push_back(make_pair((int)a[i][j], j));
dsu ac(mx);
sort(v.begin(), v.end());
for (auto& x : v) {
auto [p, t] = x;
vis[t] = 1;
if (t && vis[t - 1]) ac.merge(t - 1, t);
if (t + 1 < m && vis[t + 1]) ac.merge(t + 1, t);
t = ac.getp(t);
if (ac.l[t] && ac.r[t] + 1 < m && a[i][ac.l[t] - 1] > p && a[i][ac.r[t] + 1] > p) {
hori[i][ac.l[t]].push_back(pair<short, short>(ac.r[t] - ac.l[t] + 1, 1));
}
}
}
for (int i = 0; i < m; i++) {
vector<pair<int, int>> v;
vector<int> vis(mx, 0);
for (int j = 0; j < n; j++) v.push_back(make_pair((int)a[j][i], j));
dsu ac(mx);
sort(v.begin(), v.end());
for (auto& x : v) {
auto [p, t] = x;
vis[t] = 1;
if (t && vis[t - 1])ac.merge(t - 1, t);
if (t + 1 < n && vis[t + 1]) ac.merge(t + 1, t);
t = ac.getp(t);
if (ac.l[t] && ac.r[t] + 1 < n && a[ac.l[t] - 1][i] > p && a[ac.r[t] + 1][i] > p) {
vert[ac.l[t]][i].push_back(pair<short, short>(ac.r[t] - ac.l[t] + 1, 1));
}
}
}
long long res = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
// cout << i << "," << j << endl;
sort(hori[i][j].begin(), hori[i][j].end());
sort(vert[i][j].begin(), vert[i][j].end());
if (i + 1 < n) {
for (auto& x : hori[i][j]) {
auto tmp = lower_bound(hori[i + 1][j].begin(), hori[i + 1][j].end(), make_pair(x.first, (short)0));
if (tmp != hori[i + 1][j].end() && tmp->first == x.first)
x.second += tmp->second;
}
}
if (j + 1 < m) {
for (auto& x : vert[i][j]) {
auto tmp = lower_bound(vert[i][j + 1].begin(), vert[i][j + 1].end(), make_pair(x.first, (short)0));
if (tmp != vert[i][j + 1].end() && tmp->first == x.first)
x.second += tmp->second;
}
}
vector<pair<int, int>> bruh;
for (auto& x : vert[i][j]) bruh.push_back(make_pair((int)x.second, (int)x.first));
sort(bruh.begin(), bruh.end());
int cur = 0;
for (auto& x : hori[i][j]) {
while (cur < bruh.size() && bruh[cur].first < x.first) {
res += uwu.q(bruh[cur].second, mx - 1);
cur++;
}
uwu.upd(x.second, 1);
}
while (cur < bruh.size()) {
res += uwu.q(bruh[cur].second, mx - 1);
cur++;
}
for (auto& x : hori[i][j]) {
uwu.upd(x.second, -1);
}
}
}
return res;
}
// int32_t main() {
// int a = count_rectangles({ {4, 8, 7, 5, 6},
// { 7, 4, 10, 3, 5 },
// { 9, 7, 20, 14, 2 },
// { 9, 14, 7, 3, 6 },
// { 5, 7, 5, 2, 7 },
// {4, 5, 13, 5, 6} });
// cout << a << endl;
// }
Compilation message
rect.cpp: In constructor 'bit::bit(int)':
rect.cpp:27:24: warning: 'bit::n' will be initialized after [-Wreorder]
27 | vector<int> b; int n;
| ^
rect.cpp:27:17: warning: 'std::vector<int> bit::b' [-Wreorder]
27 | vector<int> b; int n;
| ^
rect.cpp:28:5: warning: when initialized here [-Wreorder]
28 | bit(int n) : n(n), b(n, 0) {}
| ^~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:102:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | while (cur < bruh.size() && bruh[cur].first < x.first) {
| ~~~~^~~~~~~~~~~~~
rect.cpp:108:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | while (cur < bruh.size()) {
| ~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
3 ms |
1100 KB |
Output is correct |
23 |
Correct |
4 ms |
1108 KB |
Output is correct |
24 |
Correct |
3 ms |
1108 KB |
Output is correct |
25 |
Correct |
2 ms |
852 KB |
Output is correct |
26 |
Correct |
4 ms |
880 KB |
Output is correct |
27 |
Correct |
3 ms |
852 KB |
Output is correct |
28 |
Correct |
3 ms |
852 KB |
Output is correct |
29 |
Correct |
2 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
3 ms |
1100 KB |
Output is correct |
18 |
Correct |
4 ms |
1108 KB |
Output is correct |
19 |
Correct |
3 ms |
1108 KB |
Output is correct |
20 |
Correct |
2 ms |
852 KB |
Output is correct |
21 |
Correct |
4 ms |
880 KB |
Output is correct |
22 |
Correct |
3 ms |
852 KB |
Output is correct |
23 |
Correct |
3 ms |
852 KB |
Output is correct |
24 |
Correct |
2 ms |
596 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
0 ms |
340 KB |
Output is correct |
30 |
Correct |
16 ms |
4948 KB |
Output is correct |
31 |
Correct |
18 ms |
4948 KB |
Output is correct |
32 |
Correct |
16 ms |
5064 KB |
Output is correct |
33 |
Correct |
13 ms |
3296 KB |
Output is correct |
34 |
Correct |
23 ms |
3796 KB |
Output is correct |
35 |
Correct |
19 ms |
3764 KB |
Output is correct |
36 |
Correct |
17 ms |
3772 KB |
Output is correct |
37 |
Correct |
17 ms |
3676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
3 ms |
1100 KB |
Output is correct |
18 |
Correct |
4 ms |
1108 KB |
Output is correct |
19 |
Correct |
3 ms |
1108 KB |
Output is correct |
20 |
Correct |
2 ms |
852 KB |
Output is correct |
21 |
Correct |
4 ms |
880 KB |
Output is correct |
22 |
Correct |
3 ms |
852 KB |
Output is correct |
23 |
Correct |
3 ms |
852 KB |
Output is correct |
24 |
Correct |
2 ms |
596 KB |
Output is correct |
25 |
Correct |
16 ms |
4948 KB |
Output is correct |
26 |
Correct |
18 ms |
4948 KB |
Output is correct |
27 |
Correct |
16 ms |
5064 KB |
Output is correct |
28 |
Correct |
13 ms |
3296 KB |
Output is correct |
29 |
Correct |
23 ms |
3796 KB |
Output is correct |
30 |
Correct |
19 ms |
3764 KB |
Output is correct |
31 |
Correct |
17 ms |
3772 KB |
Output is correct |
32 |
Correct |
17 ms |
3676 KB |
Output is correct |
33 |
Correct |
0 ms |
340 KB |
Output is correct |
34 |
Correct |
0 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
0 ms |
340 KB |
Output is correct |
38 |
Correct |
139 ms |
42540 KB |
Output is correct |
39 |
Correct |
115 ms |
36396 KB |
Output is correct |
40 |
Correct |
116 ms |
36436 KB |
Output is correct |
41 |
Correct |
87 ms |
30084 KB |
Output is correct |
42 |
Correct |
222 ms |
57768 KB |
Output is correct |
43 |
Correct |
193 ms |
57800 KB |
Output is correct |
44 |
Correct |
210 ms |
57892 KB |
Output is correct |
45 |
Correct |
212 ms |
54104 KB |
Output is correct |
46 |
Correct |
146 ms |
34828 KB |
Output is correct |
47 |
Correct |
158 ms |
37448 KB |
Output is correct |
48 |
Correct |
254 ms |
42992 KB |
Output is correct |
49 |
Correct |
273 ms |
43056 KB |
Output is correct |
50 |
Correct |
131 ms |
21732 KB |
Output is correct |
51 |
Correct |
137 ms |
21680 KB |
Output is correct |
52 |
Correct |
235 ms |
41756 KB |
Output is correct |
53 |
Correct |
242 ms |
41820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
1080 KB |
Output is correct |
2 |
Correct |
8 ms |
980 KB |
Output is correct |
3 |
Correct |
7 ms |
724 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
10 ms |
924 KB |
Output is correct |
6 |
Correct |
11 ms |
924 KB |
Output is correct |
7 |
Correct |
12 ms |
916 KB |
Output is correct |
8 |
Correct |
8 ms |
852 KB |
Output is correct |
9 |
Correct |
8 ms |
916 KB |
Output is correct |
10 |
Correct |
7 ms |
564 KB |
Output is correct |
11 |
Correct |
10 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
788 ms |
202196 KB |
Output is correct |
8 |
Correct |
1765 ms |
438800 KB |
Output is correct |
9 |
Correct |
1746 ms |
440788 KB |
Output is correct |
10 |
Correct |
1745 ms |
440968 KB |
Output is correct |
11 |
Correct |
326 ms |
169604 KB |
Output is correct |
12 |
Correct |
653 ms |
322060 KB |
Output is correct |
13 |
Correct |
677 ms |
343224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
3 ms |
1100 KB |
Output is correct |
18 |
Correct |
4 ms |
1108 KB |
Output is correct |
19 |
Correct |
3 ms |
1108 KB |
Output is correct |
20 |
Correct |
2 ms |
852 KB |
Output is correct |
21 |
Correct |
4 ms |
880 KB |
Output is correct |
22 |
Correct |
3 ms |
852 KB |
Output is correct |
23 |
Correct |
3 ms |
852 KB |
Output is correct |
24 |
Correct |
2 ms |
596 KB |
Output is correct |
25 |
Correct |
16 ms |
4948 KB |
Output is correct |
26 |
Correct |
18 ms |
4948 KB |
Output is correct |
27 |
Correct |
16 ms |
5064 KB |
Output is correct |
28 |
Correct |
13 ms |
3296 KB |
Output is correct |
29 |
Correct |
23 ms |
3796 KB |
Output is correct |
30 |
Correct |
19 ms |
3764 KB |
Output is correct |
31 |
Correct |
17 ms |
3772 KB |
Output is correct |
32 |
Correct |
17 ms |
3676 KB |
Output is correct |
33 |
Correct |
139 ms |
42540 KB |
Output is correct |
34 |
Correct |
115 ms |
36396 KB |
Output is correct |
35 |
Correct |
116 ms |
36436 KB |
Output is correct |
36 |
Correct |
87 ms |
30084 KB |
Output is correct |
37 |
Correct |
222 ms |
57768 KB |
Output is correct |
38 |
Correct |
193 ms |
57800 KB |
Output is correct |
39 |
Correct |
210 ms |
57892 KB |
Output is correct |
40 |
Correct |
212 ms |
54104 KB |
Output is correct |
41 |
Correct |
146 ms |
34828 KB |
Output is correct |
42 |
Correct |
158 ms |
37448 KB |
Output is correct |
43 |
Correct |
254 ms |
42992 KB |
Output is correct |
44 |
Correct |
273 ms |
43056 KB |
Output is correct |
45 |
Correct |
131 ms |
21732 KB |
Output is correct |
46 |
Correct |
137 ms |
21680 KB |
Output is correct |
47 |
Correct |
235 ms |
41756 KB |
Output is correct |
48 |
Correct |
242 ms |
41820 KB |
Output is correct |
49 |
Correct |
9 ms |
1080 KB |
Output is correct |
50 |
Correct |
8 ms |
980 KB |
Output is correct |
51 |
Correct |
7 ms |
724 KB |
Output is correct |
52 |
Correct |
0 ms |
340 KB |
Output is correct |
53 |
Correct |
10 ms |
924 KB |
Output is correct |
54 |
Correct |
11 ms |
924 KB |
Output is correct |
55 |
Correct |
12 ms |
916 KB |
Output is correct |
56 |
Correct |
8 ms |
852 KB |
Output is correct |
57 |
Correct |
8 ms |
916 KB |
Output is correct |
58 |
Correct |
7 ms |
564 KB |
Output is correct |
59 |
Correct |
10 ms |
724 KB |
Output is correct |
60 |
Correct |
0 ms |
340 KB |
Output is correct |
61 |
Correct |
788 ms |
202196 KB |
Output is correct |
62 |
Correct |
1765 ms |
438800 KB |
Output is correct |
63 |
Correct |
1746 ms |
440788 KB |
Output is correct |
64 |
Correct |
1745 ms |
440968 KB |
Output is correct |
65 |
Correct |
326 ms |
169604 KB |
Output is correct |
66 |
Correct |
653 ms |
322060 KB |
Output is correct |
67 |
Correct |
677 ms |
343224 KB |
Output is correct |
68 |
Correct |
0 ms |
340 KB |
Output is correct |
69 |
Correct |
0 ms |
340 KB |
Output is correct |
70 |
Correct |
1 ms |
340 KB |
Output is correct |
71 |
Correct |
1 ms |
340 KB |
Output is correct |
72 |
Correct |
0 ms |
340 KB |
Output is correct |
73 |
Correct |
1990 ms |
585328 KB |
Output is correct |
74 |
Correct |
1704 ms |
504416 KB |
Output is correct |
75 |
Correct |
1464 ms |
504368 KB |
Output is correct |
76 |
Correct |
1167 ms |
423532 KB |
Output is correct |
77 |
Correct |
3285 ms |
782000 KB |
Output is correct |
78 |
Correct |
2218 ms |
340232 KB |
Output is correct |
79 |
Correct |
2440 ms |
366552 KB |
Output is correct |
80 |
Correct |
3796 ms |
567016 KB |
Output is correct |
81 |
Correct |
2217 ms |
355936 KB |
Output is correct |
82 |
Correct |
2972 ms |
474736 KB |
Output is correct |
83 |
Correct |
3699 ms |
593116 KB |
Output is correct |
84 |
Correct |
2128 ms |
339276 KB |
Output is correct |
85 |
Correct |
3568 ms |
579208 KB |
Output is correct |
86 |
Correct |
3476 ms |
562364 KB |
Output is correct |
87 |
Correct |
1785 ms |
469448 KB |
Output is correct |
88 |
Correct |
3239 ms |
778500 KB |
Output is correct |
89 |
Correct |
3238 ms |
780160 KB |
Output is correct |
90 |
Correct |
3173 ms |
780248 KB |
Output is correct |