Submission #66983579

---

Source Code Expand

// 綺麗に解きなおし

#include <bits/stdc++.h>
using namespace std;

/////////////////// メイン ///////////////////

int main () {
  
  //////////////////// 入力 ////////////////////

  int n, q;
  cin >> n >> q;

  vector<int> a(q);
  for (int i=0; i<q; i++) {
    cin >> a.at(i);
  }

  //////////////// 出力変数定義 ////////////////

  vector<int> result(q);

  //////////////////// 処理 ////////////////////

  // 0マス目やn+1マス目もあると思って、
  // このマスと右隣りは色が違います、という場所の一覧
  set<int> borders;

  // 前から順に処理
  for (int i=0; i<q; i++) {

    // コードの書きやすさのため、取り出しておく
    int num = a.at(i);

    // 左隣りとの色関係
    // もともと同じ色だったなら違う色に、もともと違う色だったなら同じ色に
    if (borders.count(num-1)) {
      borders.erase(num-1);
    } else {
      borders.emplace(num-1);
    }

    // 右隣りとの色関係
    // もともと同じ色だったなら違う色に、もともと違う色だったなら同じ色に
    if (borders.count(num)) {
      borders.erase(num);
    } else {
      borders.emplace(num);
    }

    // 連続黒エリアの倍だけ、色の境界があるはず
    // つまり答えはbordersの要素数の半分
    result.at(i) = borders.size()/2;

  }

  //////////////////// 出力 ////////////////////

  for (size_t i=0; i<result.size(); i++) {
    cout << result.at(i) << endl;
  }

  //////////////////// 終了 ////////////////////

  return 0;

}

Submission Info

Judge Result