結果
| 問題 | No.649 ここでちょっとQK！ |
| ユーザー |
👑  bo9chan
|
| 提出日時 | 2023-03-23 22:35:46 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 27,796 bytes |
| コンパイル時間 | 1,540 ms |
| コンパイル使用メモリ | 162,492 KB |
| 最終ジャッジ日時 | 2024-04-27 04:33:20 |
| 合計ジャッジ時間 | 2,536 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In instantiation of 'bool TreapMultiSet<T>::erase(const T&) [with T = long long int]':
main.cpp:1005:26: required from here
main.cpp:878:27: error: cannot convert 'std::unique_ptr<TreapMultiSet<long long int>::Node, std::default_delete<TreapMultiSet<long long int>::Node> >' to 'bool' in initialization
878 | bool key_exists = eq;
| ^~
| |
| std::unique_ptr<TreapMultiSet<long long int>::Node, std::default_delete<TreapMultiSet<long long int>::Node> >
ソースコード
#ifdef __LOCAL
#include <mytemplate.hpp> // プリコンパイル済みヘッダ ~/local/include/mytemplate.hpp.gch
#else
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#endif
using namespace std;
// #include <boost/multiprecision/cpp_int.hpp>
// using bint = boost::multiprecision::cpp_int;
using int128 = __int128_t;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vvd = vector<vd>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
#define REP1(i, n) REP3(i, 0, n, 1)
#define REP2(i, s, n) REP3(i, s, n, 1)
#define REP3(i, s, n, d) for (ll i = (ll)(s); i < (ll)(n); i += (d))
#define REP_OVERLOAD(e1, e2, e3, e4, NAME, ...) NAME
#define rep(...) REP_OVERLOAD(__VA_ARGS__, REP3, REP2, REP1)(__VA_ARGS__)
#define DEP1(i, n) DEP3(i, n, -1, 1)
#define DEP2(i, n, s) DEP3(i, n, s, 1)
#define DEP3(i, n, s, d) for (ll i = (ll)(n); (ll)(s) < i; i -= (d))
#define DEP_OVERLOAD(e1, e2, e3, e4, NAME, ...) NAME
#define dep(...) DEP_OVERLOAD(__VA_ARGS__, DEP3, DEP2, DEP1)(__VA_ARGS__)
#define fore(e, a) for (auto &&e : (a))
#define len(a) (ll)(a).size()
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define th third
/********* C O N S T A N T **********/
constexpr ll INF =
LONG_LONG_MAX / 2 - 10000LL; // 4,611,686,018,427,377,903 ~= 4.6e+18, 19桁
const double PI = acos(-1);
/********* P A I R **********/
template <class T, class U>
inline pair<T, U> &operator+=(pair<T, U> &a, const pair<T, U> &b) {
a.fi += b.fi;
a.se += b.se;
return a;
}
template <class T, class U>
inline pair<T, U> &operator-=(pair<T, U> &a, const pair<T, U> &b) {
a.fi -= b.fi;
a.se -= b.se;
return a;
}
template <class T, class U>
inline pair<T, U> &operator*=(pair<T, U> &a, const pair<T, U> &b) {
a.fi *= b.fi;
a.se *= b.se;
return a;
}
template <class T, class U>
inline pair<T, U> &operator/=(pair<T, U> &a, const pair<T, U> &b) {
a.fi /= b.fi;
a.se /= b.se;
return a;
}
template <class T, class U>
inline pair<T, U> &operator%=(pair<T, U> &a, const pair<T, U> &b) {
a.fi %= b.fi;
a.se %= b.se;
return a;
}
template <class T, class U, class V>
inline pair<T, U> &operator+=(pair<T, U> &a, const V &b) {
a.fi += b;
a.se += b;
return a;
}
template <class T, class U, class V>
inline pair<T, U> &operator-=(pair<T, U> &a, const V &b) {
a.fi -= b;
a.se -= b;
return a;
}
template <class T, class U, class V>
inline pair<T, U> &operator*=(pair<T, U> &a, const V &b) {
a.fi *= b;
a.se *= b;
return a;
}
template <class T, class U, class V>
inline pair<T, U> &operator/=(pair<T, U> &a, const V &b) {
a.fi /= b;
a.se /= b;
return a;
}
template <class T, class U, class V>
inline pair<T, U> &operator%=(pair<T, U> &a, const V &b) {
a.fi %= b;
a.se %= b;
return a;
}
template <class T, class U, class V>
inline pair<T, U> operator+(pair<T, U> a, const V &b) {
a += b;
return a;
}
template <class T, class U, class V>
inline pair<T, U> operator-(pair<T, U> a, const V &b) {
a -= b;
return a;
}
template <class T, class U, class V>
inline pair<T, U> operator*(pair<T, U> a, const V &b) {
a *= b;
return a;
}
template <class T, class U, class V>
inline pair<T, U> operator/(pair<T, U> a, const V &b) {
a /= b;
return a;
}
template <class T, class U, class V>
inline pair<T, U> operator%(pair<T, U> a, const V &b) {
a %= b;
return a;
}
template <class T, class U> inline pair<T, U> operator+(pair<T, U> a) {
return a;
}
template <class T, class U> inline pair<T, U> operator-(pair<T, U> a) {
return a * (-1);
}
template <class T, class U>
istream &operator>>(istream &stream, pair<T, U> &a) {
stream >> a.fi >> a.se;
return stream;
}
template <class T, class U>
ostream &operator<<(ostream &stream, const pair<T, U> &a) {
stream << a.fi << " " << a.se;
return stream;
}
/********* V E C T O R **********/
template <class T>
inline vector<T> &operator+=(vector<T> &a, const vector<T> &b) {
assert(a.size() == b.size());
rep(i, 0, a.size()) a[i] += b[i];
return a;
}
template <class T>
inline vector<T> &operator-=(vector<T> &a, const vector<T> &b) {
assert(a.size() == b.size());
rep(i, 0, a.size()) a[i] -= b[i];
return a;
}
template <class T>
inline vector<T> &operator*=(vector<T> &a, const vector<T> &b) {
assert(a.size() == b.size());
rep(i, 0, a.size()) a[i] *= b[i];
return a;
}
template <class T>
inline vector<T> &operator/=(vector<T> &a, const vector<T> &b) {
assert(a.size() == b.size());
rep(i, 0, a.size()) a[i] /= b[i];
return a;
}
template <class T>
inline vector<T> &operator%=(vector<T> &a, const vector<T> &b) {
assert(a.size() == b.size());
rep(i, 0, a.size()) a[i] %= b[i];
return a;
}
template <class T, class U>
inline vector<T> &operator+=(vector<T> &a, const U &b) {
fore(e, a) e += b;
return a;
}
template <class T, class U>
inline vector<T> &operator-=(vector<T> &a, const U &b) {
fore(e, a) e -= b;
return a;
}
template <class T, class U>
inline vector<T> &operator*=(vector<T> &a, const U &b) {
fore(e, a) e *= b;
return a;
}
template <class T, class U>
inline vector<T> &operator/=(vector<T> &a, const U &b) {
fore(e, a) e /= b;
return a;
}
template <class T, class U>
inline vector<T> &operator%=(vector<T> &a, const U &b) {
fore(e, a) e %= b;
return a;
}
template <class T, class U>
inline vector<T> operator+(vector<T> a, const U &b) {
a += b;
return a;
}
template <class T, class U>
inline vector<T> operator-(vector<T> a, const U &b) {
a -= b;
return a;
}
template <class T, class U>
inline vector<T> operator*(vector<T> a, const U &b) {
a *= b;
return a;
}
template <class T, class U>
inline vector<T> operator/(vector<T> a, const U &b) {
a /= b;
return a;
}
template <class T, class U>
inline vector<T> operator%(vector<T> a, const U &b) {
a %= b;
return a;
}
template <class T> inline vector<T> operator+(vector<T> a) {
return a;
}
template <class T> inline vector<T> operator-(vector<T> a) {
return a * (-1);
}
template <class T> istream &operator>>(istream &stream, vector<T> &a) {
fore(e, a) stream >> e;
return stream;
}
template <class T> ostream &operator<<(ostream &stream, const vector<T> &v) {
if (v.size()) {
stream << v[0];
rep(i, 1, v.size()) cout << " " << v[i];
}
return stream;
}
template <class T>
ostream &operator<<(ostream &stream, const vector<vector<T>> &vv) {
if (vv.size()) {
stream << vv[0];
rep(i, 1, vv.size()) cout << '\n' << vv[i];
}
return stream;
}
template <class T> inline T Sum(const vector<T> &v) {
return reduce(all(v));
} // v.size() == 0 のとき T() を返す
template <class T> inline T Max(const vector<T> &v) {
assert(v.size());
return *max_element(all(v));
}
template <class T> inline T Min(const vector<T> &v) {
assert(v.size());
return *min_element(all(v));
}
template <class T> inline ll Argmax(const vector<T> &v) {
assert(v.size());
return max_element(all(v)) - v.begin();
}
template <class T> inline ll Argmin(const vector<T> &v) {
assert(v.size());
return min_element(all(v)) - v.begin();
}
template <class T, class U>
inline bool Contains(const vector<T> &v, const U &a) {
return find(all(v), a) != v.end();
}
template <class T, class U> vector<T> make_vector(int n, U v) {
return vector<T>(n, v);
}
template <class T, class... Args> auto make_vector(int n, Args... args) {
auto val = make_vector<T>(args...);
return make_vector<decltype(val)>(n, move(val));
}
/********* S E T **********/
template <class T> istream &operator>>(istream &stream, set<T> &st) {
T e;
stream >> e;
st.insert(e);
return stream;
}
template <class T> ostream &operator<<(ostream &stream, const set<T> &st) {
if (st.size()) {
auto it = st.begin();
stream << *it++;
for (; it != st.end(); it++)
cout << " " << *it;
}
return stream;
}
template <class T> inline T Max(const set<T> &st) {
assert(st.size());
return *prev(st.end());
}
template <class T> inline T Min(const set<T> &st) {
assert(st.size());
return *st.begin();
}
template <class T> inline bool Contains(const set<T> &st, T x) {
return st.find(x) != st.end();
}
/********* M U L T I S E T **********/
template <class T> istream &operator>>(istream &stream, multiset<T> &st) {
T e;
stream >> e;
st.insert(e);
return stream;
}
template <class T> ostream &operator<<(ostream &stream, const multiset<T> &st) {
if (st.size()) {
auto it = st.begin();
stream << *it++;
for (; it != st.end(); it++)
cout << " " << *it;
}
return stream;
}
template <class T> inline T Max(const multiset<T> &st) {
assert(st.size());
return *prev(st.end());
}
template <class T> inline T Min(const multiset<T> &st) {
assert(st.size());
return *st.begin();
}
template <class T> inline bool Contains(const multiset<T> &st, T x) {
return st.find(x) != st.end();
}
template <class T> inline bool EraseOne(multiset<T> &st, T x) {
auto it = st.find(x);
if (it != st.end()) {
st.erase(it);
return true;
} else
return false;
} // 要素xを1つ削除. 消せたらtrueを返す.
/********* S T R I N G **********/
template <class T> inline bool Contains(const string &s, const T &c) {
return s.find(c) != string::npos;
} // cはchar, string共に可
inline string ToUpper(const string &s) {
string t;
t.resize(s.size());
std::transform(all(s), t.begin(), ::toupper);
return t;
}
inline string ToLower(const string &s) {
string t;
t.resize(s.size());
std::transform(all(s), t.begin(), ::tolower);
return t;
}
/********* T R I O **********/
template <class T1, class T2, class T3> struct trio {
T1 first;
T2 second;
T3 third;
// コンストラクタ・代入演算子
trio() {
first = T1();
second = T2();
third = T3();
}
trio(const T1 &x) : first(x), second(x), third(x) {}
trio(const T1 &x, const T2 &y, const T3 &z)
: first(x), second(y), third(z) {}
trio(const trio &t) {
first = t.first;
second = t.second;
third = t.third;
} // コピーコンストラクタ
trio &operator=(const trio &t) {
first = t.first;
second = t.second;
third = t.third;
return *this;
}
// 比較演算子
bool operator<(const trio &t) const {
return tie(first, second, third) < tie(t.first, t.second, t.third);
}
bool operator==(const trio &t) const {
return tie(first, second, third) == tie(t.first, t.second, t.third);
}
bool operator!=(const trio &other) const {
return !(*this == other);
}
bool operator>(const trio &other) const {
return other < *this;
}
bool operator<=(const trio &other) const {
return !(*this > other);
}
bool operator>=(const trio &other) const {
return !(*this < other);
}
// 単項演算子（+ -）
trio operator+() const {
return *this;
}
trio operator-() const {
return (-1) * (*this);
}
// 複合代入演算子
trio &operator+=(const trio &t) {
first += t.first;
second += t.second;
third += t.third;
return *this;
}
trio &operator-=(const trio &t) {
first -= t.first;
second -= t.second;
third -= t.third;
return *this;
}
trio &operator*=(const trio &t) {
first *= t.first;
second *= t.second;
third *= t.third;
return *this;
}
trio &operator/=(const trio &t) {
first /= t.first;
second /= t.second;
third /= t.third;
return *this;
}
trio &operator%=(const trio &t) {
first %= t.first;
second %= t.second;
third %= t.third;
return *this;
}
// 算術演算子
friend trio operator+(const trio &lhs, const trio &rhs) {
return trio(lhs) += rhs;
}
friend trio operator-(const trio &lhs, const trio &rhs) {
return trio(lhs) -= rhs;
}
friend trio operator*(const trio &lhs, const trio &rhs) {
return trio(lhs) *= rhs;
}
friend trio operator/(const trio &lhs, const trio &rhs) {
return trio(lhs) /= rhs;
}
friend trio operator%(const trio &lhs, const trio &rhs) {
return trio(lhs) %= rhs;
}
// 入出力
friend istream &operator>>(istream &stream, trio &t) {
return stream >> t.first >> t.second >> t.third;
}
friend ostream &operator<<(ostream &stream, const trio &t) {
return stream << t.first << " " << t.second << " " << t.third;
}
operator tuple<T1 &, T2 &, T3 &>() {
return tie(first, second, third);
}
};
using tll = trio<ll, ll, ll>;
/********* R A N D O M **********/
struct Random {
mt19937_64 rnd;
Random() {
random_device seed_gen;
rnd.seed(seed_gen());
}
ll randint(ll a, ll b) { // [a, b]
uniform_int_distribution<ll> dist(a, b);
return dist(rnd);
}
double randreal(double a, double b) {
uniform_real_distribution<double> dist(a, b);
return dist(rnd);
}
char randchar(char a, char b) { // [a, b]
uniform_int_distribution<ll> dist(a, b);
return dist(rnd);
}
};
/********* P R I N T **********/
template <class T> inline void print(const T &e) {
cout << e << '\n';
}
template <class H, class... T> inline void print(const H &h, const T &...t) {
cout << h << ' ';
print(t...);
}
template <class... T> inline void End(const T &...t) {
print(t...);
exit(0);
}
/********* D E B U G **********/
#ifdef __LOCAL
#define debug(...) \
if (DEBUG) do { \
cout << '[' << #__VA_ARGS__ << "] "; \
debug_(__VA_ARGS__); \
} while (0)
#else
#define debug(...)
#endif
void dbg_(const long long &e) {
if (e == INF)
cout << "INF";
else if (e == -INF)
cout << "-INF";
else
cout << e;
}
template <class T> void dbg_(const T &e) {
cout << e;
}
template <class T, class U> void dbg_(const pair<T, U> &p) {
cout << '(';
dbg_(p.first);
cout << ' ';
dbg_(p.second);
cout << ')';
}
template <class T1, class T2, class T3> void dbg_(const trio<T1, T2, T3> &t) {
cout << '(';
dbg_(t.first);
cout << ' ';
dbg_(t.second);
cout << ' ';
dbg_(t.third);
cout << ')';
}
template <class T> void debug_(const T &e) {
dbg_(e);
cout << '\n';
}
template <class T> void debug_(const vector<T> &v) {
if (v.size()) {
auto it = v.begin();
dbg_(*it++);
for (; it != v.end(); ++it) {
cout << ' ';
dbg_(*it);
}
}
cout << '\n';
}
template <class T> void debug_(const vector<vector<T>> &vv) {
cout << '\n';
ll cnt = 0;
for (auto &&v : vv) {
cout << cnt++ << ": ";
debug_(v);
}
}
template <class T, class U> void debug_(const map<T, U> &mp) {
if (mp.size()) {
auto it = mp.begin();
dbg_(*it++);
for (; it != mp.end(); ++it) {
cout << ' ';
dbg_(*it);
}
}
cout << '\n';
}
template <class T, class U> void debug_(const vector<map<T, U>> &vm) {
cout << '\n';
ll cnt = 0;
for (auto &&mp : vm) {
cout << cnt++ << ": ";
debug_(mp);
}
}
template <class T> void debug_(const set<T> &st) {
if (st.size()) {
auto it = st.begin();
dbg_(*it++);
for (; it != st.end(); ++it) {
cout << ' ';
dbg_(*it);
}
}
cout << '\n';
}
template <class T> void debug_(const multiset<T> &st) {
if (st.size()) {
auto it = st.begin();
dbg_(*it++);
for (; it != st.end(); ++it) {
cout << ' ';
dbg_(*it);
}
}
cout << '\n';
}
template <class T> void debug_(const vector<set<T>> &vs) {
cout << '\n';
ll cnt = 0;
for (auto &&st : vs) {
cout << cnt++ << ": ";
debug_(st);
}
}
template <class T> void debug_(const vector<multiset<T>> &vs) {
cout << '\n';
ll cnt = 0;
for (auto &&st : vs) {
cout << cnt++ << ": ";
debug_(st);
}
}
template <class H, class... T> void debug_(const H &h, const T &...t) {
dbg_(h);
cout << ", ";
debug_(t...);
}
/********* O T H E R S **********/
template <class T, class U> inline bool chmin(T &a, U b) {
if (a > b) {
a = b;
return true;
}
return false;
} // bは値渡し!
template <class T, class U> inline bool chmax(T &a, U b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <class T, class U> inline auto Mod(const T &a, const U &m) {
return (a % m + m) % m;
} // 負もOK
template <class T, class U> inline auto Ceil(const T &x, const U &y) {
return x < 0 ? x / y : (x + y - 1) / y;
} // 負もOK
template <class T, class U> inline auto Floor(const T &x, const U &y) {
return -(Ceil(-x, y));
} // 負もOK
inline ll Isqrt(ll n) {
assert(n >= 0);
ll x = round(sqrt(n));
while (x * x > n)
--x;
return x;
}
inline ll Comb(ll n, ll r) {
if (r < 0 || n < r) return 0;
r = min(r, n - r);
ll ret = 1;
rep(i, r) {
ret *= n - i;
ret /= i + 1;
}
return ret;
} // n=60, r=30までOK
template <class T> inline T Pow(T x, ll n) {
assert(n >= 0);
T ret = 1;
while (1) {
if (n % 2) ret *= x;
n /= 2;
if (!n) return ret;
x = x * x;
}
} // べき乗 mintもOK
template <class T> inline T Aseries(T a, T d, ll n) {
assert(n >= 0);
return a * n + n * (n - 1) / 2 * d;
} // 等差級数 mintもOK
template <class T> inline T Gseries(T a, T r, ll n) {
assert(n >= 0);
if (r == 1)
return a * n;
else
return a * (1 - Pow(r, n)) / (1 - r);
} // 等比級数 mintもOK
template <class T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
inline bool Bit(ll b, int i) {
assert(0 <= i && i < 64);
return (b >> i) & 1;
}
inline ll Popcount(ll b) {
return __builtin_popcountll(b);
}
inline ll Mask(ll n) {
assert(0 <= n && n < 63);
return (1LL << n) - 1LL;
} // [0, n)のbitが立った64bit整数を返す。
inline ll Mask(ll n, ll m) {
assert(n >= m);
return Mask(n) ^ Mask(m);
} // [m, n)のbitが立った64bit整数を返す。
/********* M O D **********/
// #include <atcoder/modint> //
// https://atcoder.github.io/ac-library/production/document_ja/ using namespace
// atcoder; using mint = modint998244353; // modint1000000007; istream&
// operator >>(istream& stream, mint& e) {ll n; stream >> n; e = n; return
// stream; } ostream& operator <<(ostream& stream, const mint& e) { stream <<
// e.val(); return stream; } using vm = vector<mint>; using vvm = vector<vm>;
/***************************************/
constexpr bool DEBUG = true;
// 参考: https://pages.soi.ch/soiminar/treap.pdf
// verify:
template <class T> struct TreapMultiSet {
private:
struct Node {
int priority;
T key;
size_t size = 1;
size_t cnt = 1;
unique_ptr<Node> left, right;
Node(T key) : priority(rand()), key(key) {}
};
using upn = unique_ptr<Node>;
upn root;
// 分離。keyの値が含まれるとき、eq2rightがfalseならl, trueならrに行く。
pair<upn, upn> split(upn current, const T &key, bool eq2right = false) {
upn l, r;
if (!current) return {move(l), move(r)};
if (key < current->key || (key == current->key && eq2right)) {
r = move(current);
tie(l, r->left) = split(move(r->left), key, eq2right);
r->size -= (!l ? 0 : l->size);
} else {
l = move(current);
tie(l->right, r) = split(move(l->right), key, eq2right);
l->size -= (!r ? 0 : r->size);
}
return {move(l), move(r)};
}
// 結合。必要条件: l->key <= r->key
upn merge(upn l, upn r) {
if (!l || !r) return l ? move(l) : move(r);
if (l->priority > r->priority) {
l->size += r->size;
l->right = merge(move(l->right), move(r));
return l;
} else {
r->size += l->size;
r->left = merge(move(l), move(r->left));
return r;
}
}
// x未満の要素数, eq = trueならx以下
size_t index_(const T &x, bool eq) {
if (!root) return 0;
Node *current = root.get();
size_t cnt = 0;
while (current) {
int left_size = !current->left ? 0 : current->left->size;
if (current->key == x) {
cnt += left_size;
if (eq) cnt += current->cnt;
break;
} else if (current->key < x) {
cnt += left_size + current->cnt;
current = current->right.get();
} else {
current = current->left.get();
}
}
return cnt;
}
// x未満の最大値, eq = trueならkey以下.
optional<T> less_(const T &x, bool eq) {
if (!root) return nullopt;
Node *current = root.get();
T ret = T();
bool exists = false;
while (current) {
if (eq && current->key == x) return x;
if (current->key < x) {
ret = current->key;
exists = true;
current = current->right.get();
} else {
current = current->left.get();
}
}
if (exists)
return ret;
else
return nullopt;
}
// x超過の最小値, eq = trueならkey以上.
optional<T> greater_(const T &x, bool eq) {
if (!root) return nullopt;
Node *current = root.get();
T ret = T();
bool exists = false;
while (current) {
if (eq && current->key == x) return x;
if (current->key > x) {
ret = current->key;
exists = true;
current = current->left.get();
} else {
current = current->right.get();
}
}
if (exists)
return ret;
else
return nullopt;
}
public:
TreapMultiSet() {}
TreapMultiSet(const vector<T> &vec) {
fore(e, vec) insert(e);
}
// keyを追加
void insert(const T &key) {
unique_ptr<Node> l, r, eq;
tie(l, r) = split(move(root), key);
tie(l, eq) = split(move(l), key, true);
if (eq) {
eq->cnt++;
eq->size++;
root = merge(merge(move(l), move(eq)), move(r));
} else {
auto node = make_unique<Node>(key);
root = merge(merge(move(l), move(node)), move(r));
}
}
// keyを消去。消去前にkeyが存在したかを返す
bool erase(const T &key) {
unique_ptr<Node> l, r, eq;
tie(l, r) = split(move(root), key);
tie(l, eq) = split(move(l), key, true);
bool key_exists = eq;
if (eq) {
if (eq->cnt == 1) { // keyが1個しかないときはNodeを削除
eq = merge(move(eq->left), move(eq->right));
} else {
eq->cnt--;
eq->size--;
}
}
root = merge(merge(move(l), move(eq)), move(r));
return key_exists;
}
// 値xが含まれるかどうか
bool contains(const T &x) {
return count(x) > 0;
}
// 要素数
size_t size() {
if (!root) return 0;
return root->size;
}
// xの要素数
size_t count(const T &x) {
if (!root) return 0;
Node *current = root.get();
while (current) {
if (x == current->key)
return current->cnt;
else if (x < current->key)
current = current->left.get();
else
current = current->right.get();
}
return 0;
}
// index番目の値（0-origin）
T operator[](size_t index) const {
assert(root);
assert(0 <= index && index < root->size);
Node *current = root.get();
while (current) {
size_t left_size = (!current->left ? 0 : current->left->size);
if (index < left_size) {
current = current->left.get();
} else if (index >= left_size + current->cnt) {
index -= left_size + current->cnt;
current = current->right.get();
} else {
break;
}
}
return current->key;
}
// x未満の要素数
size_t index(const T &x) {
return index_(x, false);
}
// x以下の要素数
size_t index_right(const T &x) {
return index_(x, true);
}
// x未満の最大値
optional<T> lt(const T &x) {
return less_(x, false);
}
// x以下の最大値
optional<T> le(const T &x) {
return less_(x, true);
}
// x超過の最小値（upper_bound）
optional<T> gt(const T &x) {
return greater_(x, false);
}
// x以上の最小値（lower_bound）
optional<T> ge(const T &x) {
return greater_(x, true);
}
};
// Treap<ll> trp = vl{0, 0, 5}; // 0, 0, 5を挿入したインスタンスを得る
// trp.insert(3); // 挿入, 重複する値は無視
// bool erased = trp.erase(3); // 削除
// bool exists = trp.contains(3); // 存在判定
// size_t siz = trp.size(); // 要素数
// size_t cnt = trp.count(3); // 3の要素数
// ll value = trp[i]; // i番目の値, 0-indexed
// size_t num1 = trp.index(5); // 5未満の要素数
// size_t num2 = trp.index_right(5); // 5以下の要素数
// optional<ll> val1 = trp.lt(5); // 5未満の最大値. 値取り出しは val1.value()
// optional<ll> val2 = trp.le(5); // 5以下の最大値
// optional<ll> val3 = trp.gt(5); // 5超過の最小値
// optional<ll> val4 = trp.ge(5); // 5以上の最小値
int main() {
cin.tie(nullptr);
cout << fixed << setprecision(10);
ll Q, K;
cin >> Q >> K;
TreapMultiSet<ll> trp;
vl ans;
rep(q, Q) {
ll t, v;
cin >> t;
if (t == 1) {
cin >> v;
trp.insert(v);
} else {
if (len(trp) < K)
ans.pb(-1);
else {
ll val = trp[K - 1];
ans.pb(val);
trp.erase(val);
}
}
}
fore(e, ans) print(e);
}