問題

B – Colorful Lines

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

記録

• 2022/3/13　Okだが、実装が遅い。

解法

1. 最後の工程は今まで塗った色に関係なく行または列をすべて塗ることができる。
2. うしろから工程を始めて、行と列のそれぞれで塗られた回数を数える。
3. うしろから工程を始めて、\(t\) が同じですでにその行または列が塗られている場合は塗れない。
4. うしろから工程を始めて、\(t\) が異なる場合は、行または列の異なる方が塗られている数だけ塗ることができない。

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 60;
// const int INF = 1001001001;

// ARC130-B
// https://atcoder.jp/contests/arc130/tasks/arc130_b

int main() {
  int H, W, C, Q;
  cin >> H >> W >> C >> Q;

  vector<int> t(Q);
  vector<int> n(Q);
  vector<int> c(Q);

  while(0 < Q) {
    cin >> t[Q - 1] >> n[Q - 1] >> c[Q - 1];
    Q--;
  }

  vector<ll> ans(C);
  int cntH = 0;
  int cntW = 0;
  map<int, int> usedH;
  map<int, int> usedW;
  rep(i, int(t.size())) {
    int _t = t[i];
    int _n = n[i];
    int _c = c[i];
    _c--;
    _n--;
    if(_t == 1) {
      if(usedH[_n] == 0) {
        cntH++;
        ans[_c] += ll(W - cntW);
        usedH[_n] = 1;
      }
    } else {
      if(usedW[_n] == 0) {
        cntW++;
        ans[_c] += ll(H - cntH);
        usedW[_n] = 1;
      }
    }
  }

  rep(i, C) { cout << ans[i] << " "; }
  cout << endl;
  return 0;
}