提出 #74114462

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N = 8e5 + 5;
int n, cnt, cntt, ans, tmp[N * 2];
struct SQ {
    int x, y, xx, yy;
} a[N];
struct Seg {
    int l, r, x, val;
    bool operator<(const Seg &o) const {
        return x < o.x;
    }
} b[N * 2];
struct ST {
#define left now * 2
#define right now * 2 + 1
    int sum[8 * N], cnt[8 * N];
    inline void push_up(int now, int l, int r) {
        if (cnt[now])
            sum[now] = tmp[r + 1] - tmp[l];
        else if (l == r)
            sum[now] = 0;
        else
            sum[now] = sum[left] + sum[right];
    }
    inline void update(int now, int l, int r, int x, int y, int val) {
        //	cout << l << ' ' << r << endl;
        if (x <= l && r <= y) {
            cnt[now] += val;
            push_up(now, l, r);
            return;
        }
        int mid = (l + r) / 2;
        if (x <= mid)
            update(left, l, mid, x, y, val);
        if (y > mid)
            update(right, mid + 1, r, x, y, val);
        push_up(now, l, r);
    }
} st;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int H, W, h, w, n;
    cin >> H >> W >> h >> w >> n;

    int tot = (H - h + 1) * (W - w + 1);

    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        a[i].x = max(1LL, x - h + 1);
        a[i].y = max(1LL, y - w + 1);
        a[i].xx = min(H - h + 1, x);
        a[i].yy = min(W - w + 1, y);
        tmp[++cnt] = a[i].y, tmp[++cnt] = a[i].yy + 1;
    }
    sort(tmp + 1, tmp + cnt + 1);
    cnt = unique(tmp + 1, tmp + cnt + 1) - tmp - 1;
    for (int i = 1; i <= n; i++) {
        a[i].y = lower_bound(tmp + 1, tmp + cnt + 1, a[i].y) - tmp;
        a[i].yy = lower_bound(tmp + 1, tmp + cnt + 1, a[i].yy + 1) - tmp;
        b[++cntt] = Seg{a[i].y, a[i].yy, a[i].x, 1};
        b[++cntt] = Seg{a[i].y, a[i].yy, a[i].xx + 1, -1};
    }
    int nn = 2 * n;
    sort(b + 1, b + nn + 1);
    for (int i = 1; i <= nn; i++) {
        if (i > 1)
            ans += st.sum[1] * (b[i].x - b[i - 1].x);
        st.update(1, 1, cnt, b[i].l, b[i].r - 1, b[i].val);
    }
    cout << tot - ans << endl;
}

提出情報

ジャッジ結果