読者です 読者をやめる 読者になる 読者になる

AOJ1079 Cosmic Market

問題

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

解法

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

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;
}