Submission #74123239

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Event {
    ll y;
    int type;
    ll x1, x2;
    bool operator<(const Event& o) const {
        if (y != o.y) return y < o.y;
        return type > o.type;
    }
};

struct SegTree {
    int n;
    vector<int> cnt;
    vector<ll> len;
    vector<ll> xs;
    
    void init(vector<ll>& coords) {
        xs = coords;
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        n = xs.size();
        cnt.resize(4*n);
        len.resize(4*n);
    }
    
    int getIdx(ll x) {
        return lower_bound(xs.begin(), xs.end(), x) - xs.begin();
    }
    
    void pushup(int node, int l, int r) {
        if (cnt[node] > 0) {
            len[node] = xs[r] - xs[l];
        } else if (l + 1 == r) {
            len[node] = 0;
        } else {
            len[node] = len[node*2] + len[node*2+1];
        }
    }
    
    void update(int node, int l, int r, int ql, int qr, int val) {
        if (qr <= l || r <= ql) return;
        if (ql <= l && r <= qr) {
            cnt[node] += val;
            pushup(node, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(node*2, l, mid, ql, qr, val);
        update(node*2+1, mid, r, ql, qr, val);
        pushup(node, l, r);
    }
    
    void update(ll x1, ll x2, int val) {
        int l = getIdx(x1);
        int r = getIdx(x2);
        if (l < r) update(1, 0, n-1, l, r, val);
    }
    
    ll query() { return len[1]; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll H, W, h, w;
    int N;
    cin >> H >> W >> h >> w >> N;
    
    ll HR = H - h + 1;
    ll WR = W - w + 1;
    
    if (HR <= 0 || WR <= 0) {
        cout << 0 << "\n";
        return 0;
    }
    
    vector<Event> events;
    vector<ll> xs;
    
    for (int i = 0; i < N; i++) {
        ll R, C;
        cin >> R >> C;
        
        ll y1 = max(1LL, R - h + 1);
        ll y2 = min(HR, R);
        ll x1 = max(1LL, C - w + 1);
        ll x2 = min(WR, C);
        
        if (y1 > y2 || x1 > x2) continue;
        
        events.push_back({y1, 1, x1, x2 + 1});
        events.push_back({y2 + 1, -1, x1, x2 + 1});
        xs.push_back(x1);
        xs.push_back(x2 + 1);
    }
    
    if (events.empty()) {
        cout << HR * WR << "\n";
        return 0;
    }
    
    sort(events.begin(), events.end());
    
    SegTree st;
    st.init(xs);
    
    ll union_area = 0;
    ll last_y = events[0].y;
    
    for (auto& e : events) {
        ll cur_y = e.y;
        if (cur_y > last_y) {
            union_area += st.query() * (cur_y - last_y);
            last_y = cur_y;
        }
        st.update(e.x1, e.x2, e.type);
    }
    
    cout << HR * WR - union_area << "\n";
    
    return 0;
}

Submission Info

Judge Result