Untitled
unknown
c_cpp
9 months ago
1.6 kB
8
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