Untitled

 avatar
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