codeforce #295 div1 cubes

cubes.cpp

#include <set>
#include <unordered_set>
#include <algorithm>
#include <utility>
#include <cstdio>
#include <map>
using namespace std;
typedef pair<int, int> pii;
const long long mod = 1000000009;
int m, x, y;
int dir[3][2]={-1,1,0,1,1,1};
set<pii> coordinate;  //why unorder_set can't store pii? no std hash() for pair
map<pii, int> mp;

//has support from left, right?
bool has_support(int x, int y){
	if(y==0) return true;

	int res = coordinate.count(make_pair(x-1,y-1));
	res += coordinate.count(make_pair(x,y-1));
	res += coordinate.count(make_pair(x+1,y-1));
	return res>1;// have to count in where (x,y) come from
}

bool can_rm(pii target){
	int x = target.first, y = target.second;
	//use count rather than find, less typing :)
	if(coordinate.count(make_pair(x+1,y+1)))
		if(!has_support(x+1, y+1))
			return false;

	if(coordinate.count(make_pair(x,y+1)))
		if(!has_support(x, y+1))
			return false;

	if(coordinate.count(make_pair(x-1,y+1)))
		if(!has_support(x-1, y+1))
			return false;

	return true;
}

int main(){
	set<pair<int, pii>> order; 
	scanf("%d", &m);
	for(int i=0;i<m;++i){
		scanf("%d %d", &x, &y);
		coordinate.emplace(x, y);
		mp[make_pair(x,y)]=i;
	}

	// linear search would be too slow, need to keep min/max
	// this set stores cubes that can be safely removed.
	for_each(coordinate.begin(), coordinate.end(), [&order](const pii &p){
		if(can_rm(p)){
			order.emplace(mp[p],p);
		}
	});

	pair<int, pii> t;
	int big=1, num=0;
	long long ans=0;
	for(int n=0;n<m;++n){
		if(big){ 
			t = *order.rbegin();
		}
		else{
			t = *order.begin();
		}

		ans = (ans * m + t.first) % mod;   // need LL here
		order.erase(t);                    // iterator is invalidated after erase
		coordinate.erase(t.second);

		//re-check lower level 3 of me becomes available
		int x = t.second.first, y = t.second.second;
		for(int i=-1;i<=1;++i){
			pii p = make_pair(x+i,y-1);
			if(coordinate.count(p)>0 && can_rm(p)){
				order.emplace(mp[p],p);
			}
		}
		//re-check same level -2 ~ 2 becomes unavail
		for(int i=-2; i<=2; ++i){
			pii p = make_pair(x+i,y);
			auto z = make_pair(mp[p],p);
			if(coordinate.count(p)>0 && !can_rm(p)){
				order.erase(z);
			}
		}

		big = (big+1) % 2;
	}
	printf("%lld\n", ans);
	return 0;
}