問題

D – Cutting Woods

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

atcoder.jp

記録

• 2022/7/11 解法思いつかず。

解法

• setと二分探索

コード例

#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 << 62;
// const int INF = 1001001001;

// 21:28

int main() {
  int L, Q;
  cin >> L >> Q;

  set<int> ans;
  ans.insert(0);
  ans.insert(L);

  while(0 < Q) {
    int c;
    cin >> c;
    if (c == 1) {
      int x;
      cin >> x;
      ans.insert(x);
    } else {
      int x;
      cin >> x;
      auto v = ans.lower_bound(x);
      int l = *v;
      v--;
      int r = *v;
      cout << l - r << endl;
    }
    Q--;
  }

  return 0;
}