AOJ1079 Cosmic Market

問題リンク Cosmic Market

• 解法

最終的に立っている人の数が求めたい答えとなります。
同じ1列、1行に複数個のクエリが来た場合、答えに影響するのは一番最後のクエリだけです。なのでQ個のクエリを最初に全て読み込んでしまって、逆から処理していきます。処理していく中で、同じ行、列に対してクエリが来た場合これは無視します。
ある行を立たせるクエリが来たとします。このとき、まだ処理が行われていない列の数と同じ人数が最後まで立つことになります。つまり、処理を行った行の数と列の数を覚えながらクエリを処理すれば答えが求まることになります。

• ソース

import java.util.Arrays;
import java.util.Scanner;

//Cosmic Market
public class AOJ1079 {

	void run(){
		Scanner sc = new Scanner(System.in);
		boolean[] r = new boolean[50000], c = new boolean[50000];
		int[] a = new int[50000], b = new int[50000], o = new int[50000];
		for(;;){
			int R = sc.nextInt(), C = sc.nextInt(), Q = sc.nextInt();
			if((R|C|Q)==0)break;
			Arrays.fill(r, false);
			Arrays.fill(c, false);
			long res = 0;
			for(int i=0;i<Q;i++){
				a[i] = sc.nextInt(); b[i] = sc.nextInt(); o[i] = sc.nextInt();
			}
			for(int i=Q-1;i>=0;i--){
				if(o[i]==0){
					if(a[i]==0){
						if(r[b[i]])continue;
						r[b[i]] = true;
						R--;
					}
					else{
						if(c[b[i]])continue;
						c[b[i]] = true;
						C--;
					}
				}
				else{
					if(a[i]==0){
						if(r[b[i]])continue;
						r[b[i]] = true;
						res+=C;
						R--;
					}
					else{
						if(c[b[i]])continue;
						c[b[i]] = true;
						res+=R;
						C--;
					}
				}
			}
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1079().run();
	}
}