Code ac area.cpp - Đăng - Chuyên Sơn La Online Judge

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define ll long long

#define pii pair<int,int>

#define ff first

#define ss second

#define pb push_back

#define eb emplace_back

#define bug(A) cout<<A<<" hi\n";

using namespace std;

struct Event {

int x, y1, y2, type;

Event(int x, int y1, int y2, int type) : x(x), y1(y1), y2(y2), type(type) {}

};

struct SegmentTree {

vector<int> count, length;

int n;

SegmentTree(int size) : n(size) {

    count.resize(4 * n, 0);

    length.resize(4 * n, 0);

}


void update(int node, int start, int end, int l, int r, int value) {

    if (r < start || end < l) return;

    if (l <= start && end <= r) {

        count[node] += value;

    } else {

        int mid = (start + end) / 2;

        update(node * 2, start, mid, l, r, value);

        update(node * 2 + 1, mid + 1, end, l, r, value);

    }
    
    if (count[node] > 0) {
        length[node] = end - start + 1;
    } else {
        length[node] = (start == end) ? 0 : length[node * 2] + length[node * 2 + 1];
    }
}

int query() {
    return length[1];
}

};

int main() { int n; cin >> n; vector events;

int maxY = 0;
for (int i = 0; i < n; i++) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    events.emplace_back(x1, y1, y2 - 1, 1);
    events.emplace_back(x2, y1, y2 - 1, -1);
    maxY = max(maxY, y2);
}

sort(events.begin(), events.end(), [](const Event &a, const Event &b) {
    return a.x < b.x;
});

SegmentTree segTree(maxY);
int lastX = 0;
long long area = 0;

for (const auto &event : events) {
    int currentX = event.x;
    int coveredLength = segTree.query();
    area += static_cast<long long>(coveredLength) * (currentX - lastX);

    segTree.update(1, 0, maxY, event.y1, event.y2, event.type);
    lastX = currentX;
}

cout << area << endl;
return 0;

}