(C++)ABC241D - Sequence Query - 競プロはじめました

Pythonが苦手とする順序付き集合の問題なので，C++で解けるようにする（順序付集合 - 競プロはじめました）．

考え方
回答例

考え方

(C++) ABC217D - Cutting Woods - 競プロはじめましたと似ている．値に重複があるのが異なる．

順序付き集合が使えれば，あとはlower_boundとupper_boundを使ってやるだけ．

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

回答例

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

int main() {
  int Q;
  cin >> Q;
  multiset<ll> s;
  for (int i = 0; i < Q; i++) {
    int type; ll x;
    cin >> type >> x;
    if (type == 1) {
      s.insert(x);
    } else {
      int k;
      cin >> k;
      ll ans = -1;
      if (type == 2) {
        auto it = s.upper_bound(x);
        while (k > 0 && it != s.begin()) {k--; it--;}
        if (k == 0) {ans = *it;}
      } else {
        auto it = s.lower_bound(x);
        while (k > 1 && it != s.end()) {k--; it++;}
        if (k == 1 && it != s.end()) {ans = *it;}
      }
      cout << ans << endl;
    }
  }
  return 0;
}

【参考】