ABC 182: E - Akari

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int H, W, N, M;
    cin >> H >> W >> N >> M;
    vector < pair < int , int > > bulbs(N), blocks(M);
    for(auto& x : bulbs)
        cin >> x.x >> x.y;
    vector < vector < int > > lin_prev_block(H + 4, vector < int >(W + 4)),
                              lin_next_block(H + 4, vector < int >(W + 4)),
                              col_prev_block(H + 4, vector < int >(W + 4)),
                              col_next_block(H + 4, vector < int >(W + 4));
    vector < vector < bool > > block(H + 4, vector < bool >(W + 4));
    for(auto& x : blocks) {
        cin >> x.x >> x.y;
        lin_prev_block[x.x][x.y] = lin_next_block[x.x][x.y] = col_prev_block[x.x][x.y] = col_next_block[x.x][x.y] = 1;
        block[x.x][x.y] = true;
    }
    for(int i = 1; i <= H; ++i) {
        for(int j = 1; j <= W; ++j)
            if(lin_prev_block[i][j] == 1)
                lin_prev_block[i][j] = j;
            else
                lin_prev_block[i][j] = lin_prev_block[i][j - 1];
        for(int j = W; j > 0; --j)
            if(lin_next_block[i][j] == 1)
                lin_next_block[i][j] = j;
            else
                lin_next_block[i][j] = lin_next_block[i][j + 1];
    }
    for(int j = 1; j <= W; ++j) {
        for(int i = 1; i <= H; ++i)
            if(col_prev_block[i][j] == 1)
                col_prev_block[i][j] = i;
            else
                col_prev_block[i][j] = col_prev_block[i - 1][j];
        for(int i = H; i > 0; --i)
            if(col_next_block[i][j] == 1)
                col_next_block[i][j] = i;
            else
                col_next_block[i][j] = col_next_block[i + 1][j];
    }
    vector < vector < int > > lines(H + 4, vector < int >(W + 4)),
                              cols(H + 4, vector < int >(W + 4));
    for(auto x : bulbs) {
        int lin = x.x, col = x.y;
        int c1 = lin_prev_block[lin][col], c2 = lin_next_block[lin][col];
        if(c2 == 0)
            c2 = W + 1;
        int l1 = col_prev_block[lin][col], l2 = col_next_block[lin][col];
        if(l2 == 0)
            l2 = H + 1;
        ++lines[lin][c1 + 1];
        --lines[lin][c2];
        ++cols[l1 + 1][col];
        --cols[l2][col];
    }
    for(int i = 1; i <= H; ++i)
        for(int j = 1; j <= W; ++j) {
            int add = 0;
            if(lines[i][j] > 0)
                add = 1;
            if(block[i][j])
                lines[i][j] = 0;
            else
                lines[i][j] = lines[i][j - 1] + add;
        }
    for(int j = 1; j <= W; ++j)
        for(int i = 1; i <= H; ++i) {
            int add = 0;
            if(cols[i][j] > 0)
                add = 1;
            if(block[i][j])
                cols[i][j] = 0;
            else
                cols[i][j] = cols[i - 1][j] + add;
        }
    int ans = 0;
    for(int i = 1; i <= H; ++i)
        for(int j = 1; j <= W; ++j)
            if(lines[i][j] > 0 || cols[i][j] > 0)
                ++ans;
    cout << ans;
}