Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- vector<int> pai, sub;
- int find(int v) {return ((v == pai[v]) ? (v) : pai[v] = find(pai[v]));}
- void une(int a, int b)
- {
- a = find(a); b = find(b);
- if (a == b) return;
- if (sub[a] < sub[b]) swap(a, b);
- pai[b] = a;
- sub[a] += sub[b];
- }
- int32_t main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- int N;
- cin >> N;
- pai.resize(N+1); sub.resize(N+1);
- iota(pai.begin(), pai.end(), 0);
- for (auto &x : sub) x = 1;
- vector<tuple<int, int, int> > Eventos;
- vector<tuple<int, int, int, int> > v(N+1);
- // cerr << "PENIS" << '\n';
- for (int i = 1; i <= N; i++)
- {
- auto &[X, Y, W, H] = v[i];
- cin >> X >> Y >> W >> H;
- Eventos.emplace_back(X, 0, i);
- Eventos.emplace_back(X+W, 1, i);
- }
- // cerr << "PENIS" << '\n';
- sort(Eventos.begin(), Eventos.end());
- set<pair<int, int> > s;
- // cerr << "PENIS" << '\n';
- for (auto [X1, type, id] : Eventos)
- {
- auto [X, Y, W, H] = v[id];
- // cerr << X1 << " " << type << " " << id << " " << X << " " << Y << " " << W << " " << H << '\n';
- if (type == 1)
- {
- for (int i = Y; i <= Y+H-1; i++) s.erase(make_pair(i, id));
- }
- else
- {
- auto up = s.lower_bound(make_pair(Y, 0));
- while (up != s.end() && up->first <= (Y+H) && up->first >= (Y-1))
- {
- une(id, up->second);
- if (Y <= up->first && up->first <= Y+H-1) up = s.erase(up);
- else ++up;
- }
- auto low = s.upper_bound(make_pair(Y+H, 0));
- while (low != s.begin() && !s.empty() && (--low)->first >= (Y-1) && low->first <= (Y+H))
- {
- une(id, low->second);
- if (Y <= low->first && low->first <= Y+H-1) low = s.erase(low);
- }
- for (int i = Y; i <= Y+H-1; i++) s.emplace(i, id);
- }
- // cerr << "s: " << '\n';
- // cerr << X1 << ": ";
- // if (s.empty()) cerr << "-";
- // for (auto [y, id] : s) cerr << y << " ";
- // cerr << '\n';
- }
- // for (int i = 1; i <= N; i++) cerr << (i-1) << " " << (find(i)-1) << '\n';
- // cerr << '\n';
- // cerr << "PENIS" << '\n';
- vector<int> resp(N+1);
- for (int i = 1; i <= N; i++) resp[find(i)] += (get<2>(v[i])*get<3>(v[i]));
- // cerr << "PENIS" << '\n';
- int ans = 0;
- for (int i = 1; i <= N; i++) ans = max(ans, resp[i]);
- cout << ans << '\n';
- }
Add Comment
Please, Sign In to add comment
