Submission #57536430

---

Source Code Expand

// D - Cross Explosion
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

int n, m, q, cnt;
vector<set<int>> row, col;

void del(int x, int y)
{
	cnt--;
	auto it_row = row[x].find(y);
	assert(it_row != row[x].end());
	row[x].erase(it_row);
	
	auto it_col = col[y].find(x);
	assert(it_col != col[y].end());
	col[y].erase(it_col);
	
//	debug("(%d, %d) deleted\n", x, y);
}

int main()
{
	cin >> n >> m >> q;
	row.resize(n + 1), col.resize(m + 1);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) row[i].insert(j);
	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= n; j++) col[i].insert(j);
	
	cnt = n * m;
	for(int i = 1, x, y; i <= q; i++)
	{
		cin >> x >> y;
		auto it_row = row[x].lower_bound(y);
		if(*it_row == y) del(x, y);
		else
		{
			if(it_row != row[x].begin()) del(x, *(prev(it_row)));
			if(it_row!= row[x].end()) del(x, *it_row);
			
			auto it_col = col[y].lower_bound(x);
			if(it_col != col[y].begin()) del(*(prev(it_col)), y);
			if(it_col != col[y].end()) del(*it_col, y);
		}
	}
	
	cout << cnt << endl;
	
	return 0;
}

Submission Info

Judge Result