ABC217-D 解説

D - Cutting Woods

データ構造ゲーです。要素が小さい順に並んでいて、データの挿入と探索が高速にできるデータ構造としては、PythonではSortedList、C++ではsetなどがあります。

from sortedcontainers import SortedList
L, Q = map(int, input().split())
s = SortedList([0, L])
for _ in range(Q):
    c, x = map(int, input().split())
    if c == 1:
        s.add(x)
    else:
        l = s.bisect_left(x)
        print(s[l] - s[l - 1])

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

int main() {
    int L, Q;
    cin >> L >> Q;
    set<int> s;
    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 l = s.lower_bound(x);
            cout << *l - *next(l, -1) << '\n';
        }
    }
}