1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <iostream>
#include <string>
#include <cassert>
#include <algorithm>
#include <vector>
#include <unordered_set>

// Config selector:
// 1 == Debug
// 0 == Release
#if 0

// Debug config
#define ASSERT(expr) assert(expr)
#define DBG(expr) expr

#else

// Release config
#define ASSERT(expr) do {} while (0)
#define DBG(expr) do {} while (0)

#endif

using XY = std::pair<int, int>;

template<>
struct std::hash<XY>
{
	std::size_t operator()(XY const & xy) const noexcept
	{
		return xy.first ^ (xy.second << 1);
	}
};

using Cells = std::unordered_set<XY>;

XY operator+(XY const & a, XY const & b)
{
	return XY(a.first + b.first, a.second + b.second);
}

static const XY XY_LEFT  = XY(-1, 0);
static const XY XY_RIGHT = XY(1, 0);
static const XY XY_UP    = XY(0, -1);
static const XY XY_DOWN  = XY(0, 1);

auto cell_neighbour_deltas = {
	XY_LEFT,
	XY_UP,
	XY_RIGHT,
	XY_DOWN
};

bool is_algosia_removable(Cells const & board, XY const & cell)
{
	ASSERT(board.find(cell) != board.end());
	return (board.find(cell + XY_LEFT) == board.end() && board.find(cell + XY_RIGHT) == board.end()) ||
		(board.find(cell + XY_UP) == board.end() && board.find(cell + XY_DOWN) == board.end());
}

// Removes the cell from board (and from removal), adding affected cells to algosia_removable.
void apply_removal(Cells & board, Cells & algosia_removable, XY const & cell)
{
	auto it = board.find(cell);
	// assert it's on board
	ASSERT(it != board.end());
	board.erase(it);

	// same from algosia_removable, but it need not be there!
	algosia_removable.erase(cell);

	// process neighbours, perhaps adding them to algosia_removable
	for (XY const & delta : cell_neighbour_deltas)
	{
		XY const neighbour = cell + delta;
		if (board.find(neighbour) != board.end() && is_algosia_removable(board, neighbour))
			algosia_removable.insert(neighbour);
	}
}

// Adds the cell to board and possibly to algosia_removable, while also removing affected cells from algosia_removable.
void apply_addition(Cells & board, Cells & algosia_removable, XY const & cell)
{
	auto p = board.insert(cell);
	// assert it wasn't on board
	ASSERT(p.second);

	if (is_algosia_removable(board, cell))
		algosia_removable.insert(cell);

	// process neighbours, perhaps removing them from algosia_removable
	for (XY const & delta : cell_neighbour_deltas)
	{
		XY const neighbour = cell + delta;
		if (board.find(neighbour) != board.end() && !is_algosia_removable(board, neighbour))
			algosia_removable.erase(neighbour);
	}
}

// Returns number of cells that Algosia can remove from board, one by one.
// Arguments:
// * board: set of all cells on board
// * algosia_removable: set of initially algosia_removable cells
// All cells from algosia_removable must be present on board.
// Arguments are passed by value, and will be modified during computation.
int simulate_algosia_removals(Cells board, Cells algosia_removable)
{
	// We treat algosia_removable as a queue, and do in a loop:
	// * extract an element
	// * remove it from board, perhaps adding some cells to algosia_removable
	int result = 0;
	while (!algosia_removable.empty())
	{
		XY const to_remove = *algosia_removable.begin();
		++result;
		apply_removal(board, algosia_removable, to_remove);
	}
	return result;
}

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

	int n;
	int m;
	int k;
	int q;
	std::cin >> n >> m >> k >> q;

	Cells board;
	for (int i = 0; i < k; ++i)
	{
		int x, y;
		std::cin >> x >> y;
		auto p = board.insert(XY(x, y));
		ASSERT(p.second);
	}

	Cells algosia_removable;
	for (XY const & cell : board)
	{
		if (is_algosia_removable(board, cell))
			algosia_removable.insert(cell);
	}

	int result = simulate_algosia_removals(board, algosia_removable);
	std::cout << result << '\n';

	for (int i = 0; i < q; ++i)
	{
		int x, y;
		std::cin >> x >> y;
		XY const cell(x, y);
		if (board.find(cell) != board.end())
		{
			// is on board, process removal
			apply_removal(board, algosia_removable, cell);
		}
		else
		{
			// not on board: add it
			apply_addition(board, algosia_removable, cell);
		}

		result = simulate_algosia_removals(board, algosia_removable);
		std::cout << result << '\n';
	}
}