(C++) ABC217D - Cutting Woods - 競プロはじめました

Python（ABC217D - Cutting Woods - 競プロはじめました）では非常に苦労したので，C++で解けるようなるためのメモ．Pythonに比べてメチャクチャ簡単に実装できる．

考え方
回答例

考え方

ソート状態を保ったままカット位置cut = [0, ..., L]を保持できれば，$c=2$の場合に与えられた要素が$x$だとすると

*lower_bound(x) - *(lower_bound(x) - 1)

で長さが計算できる（今回，std::setを使うのでイテレータに対し-1ではなくprevを使う必要がある）．

std::setを使えば，insert，lower_bound，upper_boundはいずれも要素数の対数時間で処理できる．
【参考】set - cpprefjp C++日本語リファレンス

イテレータについては次がわかりやすい：AI - 4.04.イテレータ

回答例

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

int main() {
  int L, Q;
  cin >> L >> Q;
  set<int> s;   // intをキーとして扱う
  s.insert(0);
  s.insert(L);
  for (int i = 0; i < Q; i++) {
    int c, x;
    cin >> c >> x;
    if (c == 1) {
      s.insert(x);
    } else {
      auto top = s.lower_bound(x);
      auto bottom = prev(top, 1);
      
      cout << *top - *bottom << endl;
    }
  }
  return 0;
}

【参考】Submission #26210749 - AtCoder Beginner Contest 217