AOJ1079 Cosmic Market

問題

Cosmic Market | Aizu Online Judge
のグリッドがある。各マスには人がいて、はじめ全員が座っている。指定された行、または列に対して「立つ」または「座る」というクエリが回与えられる。最後に立っている人の数を答えよ。

解法

任意の行[列]について、その行[列]に与えられた最後のクエリの影響しか受けない。よって、クエリを逆から読み、行[列]に対しての最後のクエリが立つか座るかのいずれであるかを考えれば良い。また、各マスを重複して数えないように、行[列]に対する操作は、幅[高さ]のサイズから既に使った列[行]の数を引いて数えるという、典型(自明？)っぽいマスの数え上げの方法を使って解く。

int A[50001], B[50001], O[50001];
 
int main() {
 
  for(int R, C, Q; cin >> R >> C >> Q && R && C && Q;) {
    rep(i, Q) {
      cin >> A[i] >> B[i] >> O[i];
    }
 
    set<int> vis[2];
    int rcnt = 0, ccnt = 0;
    ll sum = 0;
 
    for(int i=Q-1; i>=0; i--) {
      if(vis[A[i]].count(B[i])) continue;
      vis[A[i]].insert(B[i]);
      if(O[i]) {
        if(A[i]) sum += R - rcnt;
        else sum += C - ccnt;
      }
      if(A[i]) ccnt ++;
      else rcnt ++;
    }
    cout << sum << endl;
  }
 
  return 0;
}