p291.ans1
======================
21
15
21

=================
p291.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int q, c, n, t;
vector<pair<int, int>> xy;

void read() {
    cin >> q >> c >> n >> t;
    xy.resize(n);
    cin >> xy;
}

void solve() {
    // We can do a simple BFS solution: each culture expands from its starting
    // position. Since cultures divide in order (1, 2, 3, ...) each second, and
    // entering an occupied cell kills the incoming bacterium, we use
    // multi-source BFS. The queue naturally processes cells in order of
    // distance, and we add cultures in index order so ties go to lower-indexed
    // cultures.

    vector<vector<int>> owner(q + 1, vector<int>(c + 1, 0));
    vector<int> ans(n + 1, 0);
    queue<tuple<int, int, int, int>> bfs;

    vector<pair<int, int>> dxy = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int dy[] = {1, 0, -1, 0};

    for(int i = 0; i < n; i++) {
        int x = xy[i].first, y = xy[i].second;
        if(x >= 1 && x <= q && y >= 1 && y <= c && owner[x][y] == 0) {
            owner[x][y] = i + 1;
            bfs.push({x, y, 0, i + 1});
        }
    }

    while(!bfs.empty()) {
        auto [x, y, ti, num] = bfs.front();
        bfs.pop();

        if(ti >= t) {
            continue;
        }

        for(auto [dx, dy]: dxy) {
            int nx = x + dx;
            int ny = y + dy;
            if(nx >= 1 && nx <= q && ny >= 1 && ny <= c && owner[nx][ny] == 0) {
                owner[nx][ny] = num;
                bfs.push({nx, ny, ti + 1, num});
            }
        }
    }

    for(int x = 1; x <= q; x++) {
        for(int y = 1; y <= c; y++) {
            ans[owner[x][y]]++;
        }
    }

    for(int i = 1; i <= n; i++) {
        cout << ans[i] << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p291.in1
======================
10 10 3 3
3 3
6 2
7 9

=================
statement.txt
======================
291. Evolution
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Qc has discovered n new amusing cultures of bacteria. The bacteria are grown in a special container divided into qxc cells. Initially one bacterium of each culture is put into some cell of the box. After that they start to grow.
Each second the following actions take place.
First the bacteria of the first culture divide simultaneously. Each bacterium divides into five ones, and if the dividing bacterium occupied the cell (x, y), the five bacteria try to occupy cells (x, y), (x-1, y), (x+1, y), (x, y-1) and (x, y+1). If the required cell does not exist, or is occupied by the bacterium of the other culture, the corresponding bacterium dies. If the cell that the bacterium goes to is already occupied by the bacterium of the same culture, the younger bacterium kills the older one and occupies the cell. If two bacteria of the same generation try to occupy the same cell, the random one wins and kills the other one.
After bacteria of the first culture divide, bacteria of the second culture do, after that the bacteria of the third culture, and so on. It takes one second for all n cultures to divide.
All cultures divide in the described way each second.
Given the initial positions of bacteria of all cultures, Qc wants to know how many cells are occupied by each culture after t seconds.

Input
The first line of the input contains four integer numbers: 1 <= q, c, <= 1000, 1 <= n <= 22204 --- the number of cultures and 0 <= t <= 10^9. Next n lines contains n pairs of integer numbers (xi, yi) --- initial positions of bacteria of each culture. No two bacteria initially occupy the same cell. Size q is for x coordinates, c is for y.

Output
Print n lines of output, each line must contain a single integer --- the answer for the i-th culture.

Sample test(s)

Input
10 10 3 3
3 3
6 2
7 9

Output
21
15
21
Author:	Anton Golubev, Petrazavodsk SU
Resource:	Anton Golubev (Hedgehog)'s Contest #2 from Annual Summer Russian Teams Meeting in Petrozavodsk State University
Date:	August 26, 2005

=================
