結果
問題 | No.649 ここでちょっとQK! |
ユーザー |
![]() |
提出日時 | 2018-02-16 09:28:39 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 185 ms / 3,000 ms |
コード長 | 4,203 bytes |
コンパイル時間 | 952 ms |
コンパイル使用メモリ | 88,308 KB |
実行使用メモリ | 11,620 KB |
最終ジャッジ日時 | 2024-12-31 08:31:00 |
合計ジャッジ時間 | 6,486 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:203:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 203 | scanf("%d%d", &n, &k); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:209:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 209 | scanf("%d", &op); | ~~~~~^~~~~~~~~~~ main.cpp:213:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 213 | scanf("%lld", &v); | ~~~~~^~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*-** 649.cc: No.649 ここでちょっとQK! - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int MAX_N = 200000;const long long LINF = 1LL << 62;/* typedef */typedef long long ll;typedef vector<int> vi;typedef queue<int> qi;typedef pair<int,int> pii;template <typename T, const int BUFSIZE>struct Treap {struct Node {T key, minkey;int fix, size;Node *left, *right;void print(int k) {printf("%d: key=%lld, minkey=%lld, fix=%d, size=%d\n",k, key, minkey, fix, size);}void print() { print(0); }};typedef Node *node;node root, nullnode, buf;Node buf0[BUFSIZE], buf1;const T TINF;Treap(T tinf): TINF(tinf) {nullnode = &buf1;nullnode->left = nullnode->right = nullnode;nullnode->key = nullnode->minkey = TINF;nullnode->fix = nullnode->size = 0;clear();srand(time(NULL));}void clear() { buf = buf0; root = nullnode; }int size() { return root->size; }void update(node& t) {t->size = 1 + t->left->size + t->right->size;t->minkey = t->key;if (t->minkey > t->left->minkey) t->minkey = t->left->minkey;if (t->minkey > t->right->minkey) t->minkey = t->right->minkey;}node gen_node(T x) {node t = buf++;t->left = t->right = nullnode;t->key = t->minkey = x;t->fix = rand();t->size = 1;return t;}void rot_l(node& k1) {node k2 = k1->right;k1->right = k2->left;k2->left = k1;update(k1);update(k2);k1 = k2;}void rot_r(node& k1) {node k2 = k1->left;k1->left = k2->right;k2->right = k1;update(k1);update(k2);k1 = k2;}void insert(node& t, T x) {if (t == nullnode)t = gen_node(x);else {if (x <= t->key) {insert(t->left, x);update(t);if (t->left->fix > t->fix) rot_r(t);}else {insert(t->right, x);update(t);if (t->right->fix > t->fix) rot_l(t);}}}void insert(T x) { insert(root, x); }void remove_node(node& t) {if (t == nullnode) return;if (t->left == nullnode || t->right == nullnode) {if (t->left == nullnode)t = t->right;elset = t->left;}else {if (t->left->fix < t->right->fix) {rot_l(t);remove_node(t->left);update(t);}else {rot_r(t);remove_node(t->right);update(t);}}}T removeat(node& t, int i) {T ret = TINF;if (t != nullnode) {int lsize = t->left->size;if (i == lsize) {ret = t->key;remove_node(t);}else if (i < lsize) {ret = removeat(t->left, i);update(t);}else {ret = removeat(t->right, i - (lsize + 1));update(t);}}return ret;}T removeat(int i) { return removeat(root, i); }void print(node t, int k, int indent) {if (t == nullnode) return;if (t != NULL) {for (int i = 0; i < indent; i++) cout << " ";t->print(k + t->left->size);print(t->left, k, indent + 1);print(t->right, k + t->left->size + 1, indent + 1);}}void print() { print(root, 0, 0); }void inorder(node t) {if (t != nullnode && t != NULL) {inorder(t->left);cout << t->key << ' ';inorder(t->right);}}void inorder() {inorder(root);cout << endl;}};/* global variables */Treap<ll,MAX_N> trp(LINF);/* subroutines *//* main */int main() {int n, k;scanf("%d%d", &n, &k);k--;int sz = 0;for (int i = 0; i < n; i++) {int op;scanf("%d", &op);if (op == 1) { // addll v;scanf("%lld", &v);trp.insert(v);sz++;//printf("1 %lld\n", v);//trp.inorder();}else { // removeif (sz <= k) puts("-1");else {ll v = trp.removeat(k);sz--;printf("%lld\n", v);}}}return 0;}