AOJ1079: Cosmic Market

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1079

方針

同一のマスに対するクエリは最後のものが有効であることに着目して
クエリを逆順に見ていけばよい。

逆順に見て既にクエリを処理したことがあればそのクエリは無視、
そうでなければ(特に起立命令なら)対象となるセル数 - fixedなセル数を加えていけばよい。

クエリ等をを順番に処理していき、最後のものが有効な問題は
逆からやると効果的な場合があるので、逆順に考えてみるというのは重要かも。
GCJJ2011,予選A問題　http://code.google.com/codejam/contest/dashboard?c=889487
もそうでした。

以下ソースコード

#include <iostream>
#include <cstring>

using namespace std;

int main(void){
	int qs[3][50000];
	bool decided[2][50000];
	
	int h,w,q;
	while(cin >> h >> w >> q){
		if(!(h|w|q)) break;
		
		memset(qs,0,sizeof(qs));
		memset(decided, false, sizeof(decided));
		long long ret = 0;
		int nrow = 0 ,ncol = 0;
		for(int i=0;i<q;i++){
			cin >> qs[0][i] >> qs[1][i] >> qs[2][i];
		}
		
		for(int i=q-1;i>=0;i--){
			if(qs[0][i] == 0){
				//query for a row
				if(decided[0][qs[1][i]]) continue;
				if(qs[2][i] == 1) ret += w - ncol;
				decided[0][qs[1][i]] = true;
				nrow++;
			}else{
				//query for a col
				if(decided[1][qs[1][i]]) continue;
				if(qs[2][i] == 1) ret += h - nrow;
				decided[1][qs[1][i]] = true;
				ncol++;
			}
		}
		cout << ret << endl;
	}
}