Untitled
unknown
c_cpp
2 years ago
1.6 kB
32
Indexable
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int tt, tc;
void solve() {
int n;
cin >> n;
vector<tuple<int, int, int, int>> rectangles(n);
for (auto& [x1, y1, x2, y2] : rectangles) {
cin >> x1 >> y1 >> x2 >> y2;
}
rectangles.insert(rectangles.begin(), make_tuple(0, 0, 0, 0));
vector<pair<int, int>> events;
for (int i = 1; i <= n; i++) {
auto& [x1, y1, x2, y2] = rectangles[i];
events.emplace_back(x1, -i);
events.emplace_back(x2, i);
}
sort(events.begin(), events.end());
vector<bool> active(n + 1);
int ans = 0;
for (auto& [x, index] : events) {
bool is_start = (index < 0);
index = abs(index);
if (is_start) active[index] = 1;
vector<pair<int, int>> verevents;
for (int j = 1; j <= n; j++) if (active[j]) {
auto& [x1, y1, x2, y2] = rectangles[j];
verevents.emplace_back(y1, -j);
verevents.emplace_back(y2, j);
}
sort(verevents.begin(), verevents.end());
int num_active = 0;
for (auto& [y, verindex] : verevents) {
bool veris_start = (verindex < 0);
verindex = abs(verindex);
if (veris_start) num_active += 1;
ans = max(ans, num_active);
if (!veris_start) num_active -= 1;
}
if (!is_start) active[index] = 0;
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
tt = 1, tc = 1; // cin >> tt;
while (tt--) solve(), tc++;
}
Editor is loading...
Leave a Comment