結果

問題 No.649 ここでちょっとQK!
ユーザー tnakao0123tnakao0123
提出日時 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);
      |       ~~~~~^~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

/* -*- 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;
else
t = 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) { // add
ll v;
scanf("%lld", &v);
trp.insert(v);
sz++;
//printf("1 %lld\n", v);
//trp.inorder();
}
else { // remove
if (sz <= k) puts("-1");
else {
ll v = trp.removeat(k);
sz--;
printf("%lld\n", v);
}
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0