Submission #74129584

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

int main() {
    int H, W, h, w, N;
    cin >> H >> W >> h >> w >> N;
    
    vector<int> blockT(N), blockB(N), blockL(N), blockR(N);

    vector<pair<pair<int, int>, int>> actI;
    vector<int> actPoints;
    for (int i = 0; i < N; ++i) {
        int r, c; cin >> r >> c;
        blockT[i] = r-h+1, blockB[i] = r; // not doing max(..., 1)
        blockL[i] = max(c-w+1, 1), blockR[i] = c;
        actI.push_back({{blockL[i], +1}, i});
        actI.push_back({{blockR[i]+1, -1}, i});
        actPoints.push_back(blockL[i]);
        actPoints.push_back(blockR[i]+1);
    }
    sort(actI.begin(), actI.end());
    sort(actPoints.begin(), actPoints.end());
    actPoints.resize(unique(actPoints.begin(), actPoints.end()) - actPoints.begin());

    int lastRow = H - h + 1, lastCol = W - w + 1;

    long long blockedArea = 0;
    map<int, int> segmentStart;
    int blockedRows = 0, sectionStart = 1;
    int nextAct = 0;

    auto findRange = [&](int b) {
        int from = blockT[b], to = blockB[b];
        auto it = segmentStart.lower_bound(blockT[b]);
        if (it != segmentStart.begin()) {
            auto it2 = prev(it);
            from = max(from, it2->first+h);
        }
        if (it != segmentStart.end()) {
            to = min(to, it->first-1);
        }
        return pair<int, int>{from, to};
    };
    auto changeSeg = [&](int from, int to, int sign) {
        from = max(from, 1);
        to = min(to, lastRow);
        if (from <= to) blockedRows += (to-from+1)*sign;
    };

    for (int c : actPoints) {
        if (c > lastCol) break;
        blockedArea += (long long)blockedRows * (c - sectionStart);
        sectionStart = c;

        while (nextAct < (int)actI.size() && actI[nextAct].first.first == c) {
            auto [pr, b] = actI[nextAct];
            int action = pr.second;

            if (action == -1) { // remove segment
                segmentStart[blockT[b]]--;
                if (segmentStart[blockT[b]] == 0) segmentStart.erase(blockT[b]);
                auto [from, to] = findRange(b);
                changeSeg(from, to, -1);
            } else { // add segment
                auto [from, to] = findRange(b);
                changeSeg(from, to, +1);
                segmentStart[blockT[b]]++;
            }

            ++nextAct;
        }
    }

    blockedArea += (long long)blockedRows * (lastCol+1 - sectionStart);

    cout << (long long)lastRow*lastCol - blockedArea << endl;
    return 0;
}

Submission Info

Judge Result