ICPCOOC2016 C: Distribution Center

問題

長いレーンのベルトコンベアが 列ある。はじめ各ベルトコンベアにはその番号の種類の品物のみが乗っている。隣接するベルトコンベアの間の位置に、 個のアームが存在する。これらは上下に隣接するレール間で品物を動かすことができる。レーンを抜けたときにそれぞれのレーンで最大何種類の品物が流れてくるか。

解法

番目に対して、上端と下端を持てば良い。それぞれの配列の初期値は

minpos[i] = i;
maxpos[i] = i;

時系列順にアームをソートした上で、アームの位置を として以下のように更新できる。

minpos[y + 1] = min(minpos[y + 1], minpos[y]);
maxpos[y] = max(maxpos[y], maxpos[y + 1]);

int main() {
 
  int N, M; cin >> N >> M;
  vector<pair<int, int>> vs;
  rep(i, M) {
    int x, y; cin >> x >> y; y--;
    vs.emplace_back(x, y);
  }
 
  sort(vs.begin(), vs.end());
 
  int mins[N], maxs[N];
  rep(i, N) {
    mins[i] = i;
    maxs[i] = i;
  }
 
  rep(i, vs.size()) {
    int _, y; tie(_, y) = vs[i];
    mins[y + 1] = min(mins[y + 1], mins[y]);
    maxs[y] = max(maxs[y], maxs[y + 1]);
  }
 
  rep(i, N) {
    if(i) cout << " ";
    cout << maxs[i] - mins[i] + 1;
  }
  cout << endl;
 
  return 0;
}

感想

オープンコンテスト本番は空白区切りの出力を誤って改行区切りにしていてミスの発見にだいぶ時間がかかった。