結果
問題 | No.649 ここでちょっとQK! |
ユーザー |
![]() |
提出日時 | 2021-01-19 07:22:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,051 ms / 3,000 ms |
コード長 | 6,525 bytes |
コンパイル時間 | 5,132 ms |
コンパイル使用メモリ | 331,388 KB |
最終ジャッジ日時 | 2025-01-18 02:30:19 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
//#pragma warning(disable:4996)//#include <Windows.h>#include <iostream>#include <vector>#include <limits.h>#include <algorithm>#include <string>#include <math.h>#include <limits.h>#include <queue>#include <map>#include <set>#include <iomanip>#include <bitset>#include <cassert>#include <random>#include <functional>#include <stack>#include <iomanip>#include <cassert>#include <boost/multiprecision/cpp_int.hpp>#include <complex>#include <cstdio>#include <list>#include <bitset>//#include <stdio.h>//< in.txt > out.txtusing namespace std;//std::ios::sync_with_stdio(false);//std::cin.tie(0);const long long MOD = 1e9 + 7;const long long INF = 1e18;typedef long long LL;typedef long double LD;typedef boost::multiprecision::cpp_int bigint;typedef pair<LL, LL> PLL;typedef pair<int, int> PI;typedef pair<LD, LL> pdl;typedef pair<LD, LD> pdd;typedef vector<LL> VLL;typedef vector<VLL> VVLL;typedef vector<int> VI;typedef vector<vector<int>> VVI;typedef unsigned long long ULL;template<class T>using pqueue = priority_queue<T, vector<T>, function<bool(T, T)>>;template<class T>inline void chmin(T& a, T b) {a = min(a, b);}template<class T>inline void chmax(T& a, T b) {a = max(a, b);}void input();void solve();void daminput();void naive();void outputinput();int main() {std::cin.tie(0);std::ios::sync_with_stdio(false);input();//daminput();solve();//naive();//outputinput();return 0;}////////////////////////////////////////////////////////////////////////////////////////////////////void input() {}void daminput() {}//class Rng {//public:// Rng();// friend ostream operator<<(ostream&,Rng); (if print neccesary)//};//Rng operator+(Rng, Rng);class T {public:LL v;T() :v(1e7) {};T(LL _v) :v(_v) {};};T operator+(T a, T b) {if (a.v < b.v)return b;else return a;}//数列タイプのtreap//Xorshiftunsigned int Xorshift() {static unsigned int tx = 123456789, ty = 362436069, tz = 521288629, tw = 88675123;unsigned int tt = (tx ^ (tx << 11));tx = ty; ty = tz; tz = tw;return (tw = (tw ^ (tw >> 19)) ^ (tt ^ (tt >> 8)));}template<class Rng>class node_t {public:Rng val; //値node_t<Rng>* ch[2]; //子LL pri; //優先度LL cnt; //子の個数Rng sum; //値の和static LL node_count; //プール用の要素を数える変数static const LL MAX_N = 4000000 + 10; //プールのサイズvoid* operator new(std::size_t) {static node_t<Rng> pool[MAX_N]; //プールreturn pool + node_count++;}static void delete_all() {node_count = 0;}node_t(Rng v) {val = v;ch[0] = ch[1] = NULL;cnt = 1;sum = v;pri = Xorshift();}node_t() {val = Rng();ch[0] = ch[1] = NULL;cnt = 1;sum = val;pri = Xorshift();}node_t<Rng>* update() {node_t<Rng>* t = this;t->cnt = (t->ch[0] ? t->ch[0]->cnt : 0) + (t->ch[1] ? t->ch[1]->cnt : 0) + 1;if (t->ch[0])t->sum = t->ch[0]->sum + t->val;else t->sum = t->val;if (t->ch[1])t->sum = t->sum + t->ch[1]->sum;return t;}};template<class Rng>LL node_t<Rng>::node_count = 0;//2つのtreapをマージtemplate<class Rng>node_t<Rng>* merge(node_t<Rng>* l, node_t<Rng>* r) {if (!l || !r)return !l ? r : l;if (l->pri > r->pri) {l->ch[1] = merge(l->ch[1], r);return l->update();}else {r->ch[0] = merge(l, r->ch[0]);return r->update();}}//treapを[0,k)と[k,n)にsplittemplate<class Rng>pair<node_t<Rng>*, node_t<Rng>*> split(node_t<Rng>* t, LL k) {typedef pair<node_t<Rng>*, node_t<Rng>*> P;if (!t)return P(NULL, NULL);LL count = t->ch[0] ? t->ch[0]->cnt : 0;if (k <= count) {P s = split(t->ch[0], k);t->ch[0] = s.second;return P(s.first, t->update());}else {P s = split(t->ch[1], k - count - 1);t->ch[1] = s.first;return P(t->update(), s.second);}}//treap trの場所kに要素tを追加template<class Rng>node_t<Rng>* insert(node_t<Rng>* tr, LL k, node_t<Rng>* t) {auto sp = split(tr, k);sp.first = merge(sp.first, t);return merge(sp.first, sp.second);}//treap trの場所kの要素を消去template<class Rng>node_t<Rng>* erase(node_t<Rng>* tr, LL k) {auto sp = split(tr, k);auto sp2 = split(sp.second, 1);//delete sp2.first;return merge(sp.first, sp2.second);}template<class Rng>void print(node_t<Rng>* root) {if (root == NULL)return;print(root->ch[0]);cout << " " << root->val;print(root->ch[1]);return;}template<class Rng>node_t<Rng>* index(node_t<Rng>* root, LL n) {if (!root)return NULL;if (n >= root->cnt)return NULL;LL ln = (root->ch[0] ? root->ch[0]->cnt : 0);LL rn = (root->ch[1] ? root->ch[1]->cnt : 0);if (n < ln)return index(root->ch[0], n);else if (n == ln)return root;else return index(root->ch[1], n - (ln + 1));}template<class Rng>node_t<Rng>* change(node_t<Rng>* root, LL n, Rng x) {if (!root)return NULL;LL ln = (root->ch[0] ? root->ch[0]->cnt : 0);LL rn = (root->ch[1] ? root->ch[1]->cnt : 0);if (n >= ln + rn + 1)return NULL;if (n < ln) {node_t<Rng>* r = change(root->ch[0], n, x);root->update();return r;}else if (n == ln) {root->val = x;root->update();return root;}else {node_t<Rng>* r = change(root->ch[1], n - (ln + 1), x);root->update();return r;}}//[l,r]template<class Rng>Rng rangesum(node_t<Rng>* root, LL l, LL r) {if (root == NULL)return Rng();LL ln = (root->ch[0] ? root->ch[0]->cnt : 0);LL rn = (root->ch[1] ? root->ch[1]->cnt : 0);if (r < 0 || l > ln + rn)return Rng();l = max((LL)0, l);r = min(ln + rn, r);if (l == 0 && r == ln + rn)return root->sum;Rng ans = rangesum(root->ch[0], l, r);if (l <= ln && ln <= r)ans = ans + root->val;ans = ans + rangesum(root->ch[1], l - ln - 1, r - ln - 1);return ans;}int Q, K;void solve() {cin >> Q >> K;node_t<T>* node = nullptr;for (int q = 0; q < Q; q++) {int type;cin >> type;if (type == 1) {LL v;cin >> v;if (node == nullptr) {node = new node_t<T>(T(v));}else {int s = -1, e = node->cnt;while (e - s > 1) {int mid = (e + s) / 2;if (index(node, mid)->val.v < v)s = mid;else e = mid;}node = insert(node, e, new node_t<T>(T(v)));}}else {if (node == nullptr) {cout << -1 << "\n";}else if (K > (node->cnt)) {cout << -1 << "\n";}else {auto elem = index(node, K - 1);cout << elem->val.v << "\n";node = erase(node, K - 1);}}}}void naive() {}void outputinput() {}