1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| #include <bits/stdc++.h>
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#define MAX_N 50505
#define INF 987654321
#define ll long long
#define pll pair<ll, ll>
#define vpll vector<pll>
#define vall3 vector<array<ll,3>>
#define all5 array<ll,5>
#define vall5 vector<all5>
#define vll vector<ll>
#define vs vector<string>
#define usll unordered_set<ll>
#define vvs vector<vs>
#define vvll vector<vll>
#define all(a) begin(a), end(a)
using namespace std;
struct Line {
ll from, to;
Line operator + (const array<ll,3>& line) {
return {min(from, line[0]), max(to, line[1])};
}
};
bool overlap(Line& line1, array<ll,3>& line2) {
if(line1.from >= line2[0]) return line2[1] < line1.from;
if(line1.from < line2[0]) return line1.to >= line2[0];
return false;
}
ll uf[MAX_N], area[MAX_N];
unordered_map<ll,vall3> xline, yline;
ll n;
ll find(ll u) {
return uf[u] == u ? u : uf[u] = find(uf[u]);
}
void merge(ll u, ll v) {
ll pu = find(u), pv = find(v);
uf[pu] = uf[pv] = min(pu, pv);
}
void helper(vall3& line) {
if(line.empty()) return;
sort(all(line));
ll idx = line[0][2];
Line dummy{line[0][0], line[0][1]};
for(auto& l : line) {
if(overlap(dummy, l)) {
dummy = dummy + l;
merge(idx, l[2]);
} else {
dummy.from = l[0], dummy.to = l[1], idx = l[2];
}
}
}
ll solve() {
for(auto& [_, line] : xline)
helper(line);
for(auto& [_, line] : yline)
helper(line);
ll res = 0;
unordered_map<ll, ll> umll;
for(ll i = 0; i < n; i++) {
ll pi = find(i);
res = max(res, umll[pi] += area[i]);
}
return res;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed);
cout.precision(8);
cin >> n;
for (ll i = 0, x, y, w, h; i < n; i++) {
cin >> x >> y >> w >> h;
xline[x].push_back({y,y+h, i});
xline[x+w].push_back({y,y+h, i});
yline[y].push_back({x,x+w, i});
yline[y+h].push_back({x,x+w, i});
area[i] = w * h;
uf[i] = i;
}
cout << solve() << '\n';
return 0;
}
|
