use std::{ cmp::Ordering, ptr::{self, null_mut}, }; macro_rules! read_line { ($($xs: tt)*) => { let mut buf = String::new(); std::io::stdin().read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); expand!(iter, $($xs)*); }; } macro_rules! expand { ($iter: expr,) => {}; ($iter: expr, mut $var: ident : $type: tt, $($xs: tt)*) => { let mut $var = value!($iter, $type); expand!($iter, $($xs)*); }; ($iter: expr, $var: ident : $type: tt, $($xs: tt)*) => { let $var = value!($iter, $type); expand!($iter, $($xs)*); }; } macro_rules! value { ($iter:expr, ($($type: tt),*)) => { ($(value!($iter, $type)),*); }; ($iter: expr, [$type: tt; $len: expr]) => { (0..$len).map(|_| value!($iter, $type)).collect::>() }; ($iter: expr, Chars) => { value!($iter, String).chars().collect::>>() }; ($iter: expr, $type: ty) => { if let Some(v) = $iter.next() { v.parse::<$type>().ok() } else { None } }; } #[derive(Clone, PartialEq, Eq)] struct SplayNode { key: isize, left: *mut Self, right: *mut Self, parent: *mut Self, size: usize, } impl SplayNode { fn new(key: isize) -> Self { SplayNode { key, left: null_mut(), right: null_mut(), parent: null_mut(), size: 1, } } fn update(&mut self) { unsafe { self.size = 1; if !self.left.is_null() { self.size += (*(self.left)).size; } if !self.right.is_null() { self.size += (*(self.right)).size; } } } fn rotate(&mut self) { unsafe { let mut p = self.parent; let mut pp = (*p).parent; let mut c; if (*p).left == self { c = self.right; self.right = p; (*p).left = c; } else { c = self.left; self.left = p; (*p).right = c; } if !pp.is_null() { if (*pp).left == p { (*pp).left = self; } if (*pp).right == p { (*pp).right = self; } } self.parent = pp; (*p).parent = self; if !c.is_null() { (*c).parent = p; } (*p).update(); self.update(); } } fn state(&self) -> isize { unsafe { if !self.parent.is_null() && ptr::eq((*self.parent).left, self) { 1 } else if !self.parent.is_null() && ptr::eq((*self.parent).right, self) { -1 } else { 0 } } } fn splay(&mut self) { unsafe { while !self.parent.is_null() { if (*self.parent).state() == 0 { // zig self.rotate(); } else if (*self).state() == (*self.parent).state() { // zig-zag (*self.parent).rotate(); (*self).rotate(); } else { // zig-zig (*self).rotate(); (*self).rotate(); } } } } fn get(&mut self, mut idx: usize) -> *mut SplayNode { let mut root = self as *mut SplayNode; unsafe { loop { let lsize = if !(*root).left.is_null() { (*(*root).left).size } else { 0 }; match idx.cmp(&lsize) { Ordering::Less => { root = (*root).left; } Ordering::Equal => { (*root).splay(); return root; } Ordering::Greater => { root = (*root).right; idx = idx - lsize - 1; } } } } } fn lower_bound(&mut self, x: isize) -> usize { let root = self as *mut SplayNode; unsafe { if x <= (*root).key { if (*root).left.is_null() { return 0; } else { (*(*root).left).lower_bound(x) } } else { (if (*root).left.is_null() { 0 } else { (*(*root).left).size }) + if (*root).right.is_null() { 0 } else { (*(*root).right).lower_bound(x) } + 1 } } } fn merge(&mut self, mut r_root: *mut SplayNode) -> *mut SplayNode { let mut l_root = self as *mut SplayNode; unsafe { if l_root.is_null() { r_root } else if r_root.is_null() { l_root } else { l_root = (*l_root).get((*l_root).size - 1); (*l_root).right = r_root; (*r_root).parent = l_root; (*l_root).update(); l_root } } } fn split(&mut self, idx: usize) -> (*mut SplayNode, *mut SplayNode) { let mut root = self as *mut SplayNode; unsafe { if idx == 0 { return (null_mut(), root); } if idx == (*root).size { return (root, null_mut()); } root = (*root).get(idx); let mut l_root = (*root).left; let mut r_root = root; (*r_root).left = null_mut(); (*l_root).parent = null_mut(); (*r_root).update(); (l_root, r_root) } } fn insert(&mut self, node: *mut SplayNode) -> *mut SplayNode { let root = self as *mut SplayNode; let idx = unsafe { (*root).lower_bound((*node).key) }; let (l_root, r_root) = unsafe { (*root).split(idx) }; let temp = unsafe { (*l_root).merge(node) }; unsafe { (*temp).merge(r_root) } } fn remove(&mut self, idx: usize) -> (*mut SplayNode, *mut SplayNode) { let mut root = self as *mut SplayNode; unsafe { root = (*root).get(idx); let mut l_root = (*root).left; let mut r_root = (*root).right; if !l_root.is_null() { (*l_root).parent = null_mut() }; if !r_root.is_null() { (*r_root).parent = null_mut() }; (*root).left = null_mut(); (*root).right = null_mut(); (*root).update(); ((*l_root).merge(r_root), root) } } } pub struct SplayBST { root: *mut SplayNode, } impl SplayBST { fn new() -> Self { SplayBST { root: null_mut() } } fn insert(&mut self, x: isize) { let add = Box::into_raw(Box::new(SplayNode::new(x))); if (self.root as *mut SplayNode).is_null() { self.root = add; } else { unsafe { self.root = (*(*self).root).insert(add); } } } fn get(&mut self, idx: usize) -> Option { unsafe { if (*self).root.is_null() { return None; } if (*(*self).root).size <= idx { return None; } self.root = (*self.root).get(idx); if self.root.is_null() { None } else { Some((*self.root).key) } } } fn remove(&mut self, x: isize) { unsafe { let idx = (*(*self).root).lower_bound(x); self.root = (*(*self).root).remove(idx).0; } } } fn main() { read_line! { q: usize, k: usize, } let (q, k) = (q.unwrap(), k.unwrap()); let mut bst = SplayBST::new(); for _ in 0..q { read_line! { t: usize, v: isize, } let t = t.unwrap(); if t == 1 { let v = v.unwrap(); bst.insert(v); } else { if let Some(v) = bst.get(k - 1) { println!("{}", v); bst.remove(v); } else { println!("-1"); } } } }