use proconio::{fastout, input}; use reprol::ds::avl_tree_multi_set::AvlTreeMultiSet; #[fastout] fn main() { input! { q: usize, k: usize, } let mut ms = AvlTreeMultiSet::new(); for _ in 0..q { input! { t: i32, } if t == 1 { input! { v: u64, } ms.insert(v); } else { if ms.len() >= k { let ans = ms.remove_by_index(k - 1).unwrap(); println!("{}", ans); } else { println!("-1"); continue; } } } } #[allow(dead_code)] pub mod reprol { pub mod ds { pub mod avl_tree_multi_set { use crate::reprol::ds::avl_tree_vec::{AvlTreeVec, IntoIter, Iter}; use std::{ cmp::Ordering, fmt::Debug, hash::Hash, mem::{swap, take}, ops::Index, }; pub struct AvlTreeMultiSet { vec: AvlTreeVec, } impl AvlTreeMultiSet { pub fn new() -> Self { Self::default() } pub fn clear(&mut self) { *self = Self::new(); } pub fn len(&self) -> usize { self.vec.len() } pub fn is_empty(&self) -> bool { self.vec.is_empty() } pub fn insert(&mut self, value: T) -> bool where T: Ord, { let i = self.vec.lower_bound(&value); self.vec.insert(i, value); true } pub fn contains(&self, value: &T) -> bool where T: Ord, { let i = self.vec.lower_bound(value); self.vec.get(i).is_some_and(|e| e == value) } pub fn count(&self, value: &T) -> usize where T: Ord, { self.vec.upper_bound(value) - self.vec.lower_bound(value) } pub fn remove(&mut self, value: &T) -> bool where T: Ord, { let i = self.vec.lower_bound(value); if self.vec.get(i).is_some_and(|e| e == value) { self.vec.remove(i); true } else { false } } pub fn remove_by_index(&mut self, index: usize) -> Option { self.vec.remove(index) } pub fn append(&mut self, other: &mut Self) where T: Ord, { if self.len() < other.len() { swap(self, other); } take(&mut other.vec).into_iter().for_each(|item| { self.insert(item); }); } pub fn split_off(&mut self, value: &T) -> Self where T: Ord, { let i = self.vec.lower_bound(value); let sub = self.vec.split_off(i); Self { vec: sub } } pub fn nth(&self, index: usize) -> Option<&T> { self.vec.get(index) } pub fn nth_back(&self, index: usize) -> Option<&T> { self.vec.get(self.vec.len().checked_sub(index + 1)?) } pub fn iter(&self) -> Iter<'_, T> { self.vec.iter() } } impl Default for AvlTreeMultiSet { fn default() -> Self { Self { vec: AvlTreeVec::default(), } } } impl Index for AvlTreeMultiSet { type Output = T; fn index(&self, index: usize) -> &Self::Output { self.nth(index).unwrap() } } impl<'a, T> IntoIterator for &'a AvlTreeMultiSet { type IntoIter = Iter<'a, T>; type Item = &'a T; fn into_iter(self) -> Self::IntoIter { self.iter() } } impl IntoIterator for AvlTreeMultiSet { type IntoIter = IntoIter; type Item = T; fn into_iter(self) -> Self::IntoIter { self.vec.into_iter() } } impl PartialEq for AvlTreeMultiSet { fn eq(&self, other: &Self) -> bool { self.iter().eq(other.iter()) } } impl Eq for AvlTreeMultiSet {} impl PartialOrd for AvlTreeMultiSet { fn partial_cmp(&self, other: &Self) -> Option { self.iter().partial_cmp(other.iter()) } } impl Ord for AvlTreeMultiSet { fn cmp(&self, other: &Self) -> Ordering { self.iter().cmp(other.iter()) } } impl Hash for AvlTreeMultiSet { fn hash(&self, state: &mut H) { self.iter().for_each(|item| item.hash(state)); } } impl Extend for AvlTreeMultiSet { fn extend>(&mut self, iter: I) { iter.into_iter().for_each(|x| { self.insert(x); }); } } impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for AvlTreeMultiSet { fn extend>(&mut self, iter: I) { self.extend(iter.into_iter().cloned()); } } impl FromIterator for AvlTreeMultiSet { fn from_iter>(iter: I) -> Self { let mut res = Self::new(); res.extend(iter); res } } impl From> for AvlTreeMultiSet { fn from(v: Vec) -> Self { Self::from_iter(v) } } impl From<[T; N]> for AvlTreeMultiSet { fn from(v: [T; N]) -> Self { Self::from_iter(v) } } impl Clone for AvlTreeMultiSet { fn clone(&self) -> Self { Self { vec: self.vec.clone(), } } } impl Debug for AvlTreeMultiSet { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { f.debug_set().entries(self.iter()).finish() } } } pub mod avl_tree_vec { use std::{ cmp::Ordering, fmt::Debug, hash::Hash, marker::PhantomData, ops::{Index, IndexMut}, ptr::NonNull, }; struct Node { value: T, len: usize, height: i32, left: Link, right: Link, } type NodePtr = NonNull>; type Link = Option>; impl Node { fn new(value: T) -> NodePtr { let node = Self { value, len: 1, height: 1, left: None, right: None, }; NonNull::from(Box::leak(Box::new(node))) } #[inline] fn fetch(&mut self) { self.len = len(self.left) + len(self.right) + 1; self.height = height(self.left).max(height(self.right)) + 1; } } #[inline] fn free(node: NodePtr) { unsafe { drop(Box::from_raw(node.as_ptr())) }; } #[inline] fn len(node: Link) -> usize { node.map_or(0, |node| unsafe { node.as_ref() }.len) } #[inline] fn height(node: Link) -> i32 { node.map_or(0, |node| unsafe { node.as_ref() }.height) } #[inline] fn diff_height(node: Link) -> i32 { node.map_or(0, |node| { let node = unsafe { node.as_ref() }; height(node.left) - height(node.right) }) } fn balance(mut root: Link) -> Link { fn rotate_right(root: &mut Link) { *root = { unsafe { let mut root = root.unwrap(); let raw_root = root.as_mut(); let mut left = raw_root.left.unwrap(); let raw_left = left.as_mut(); raw_root.left = raw_left.right; raw_root.fetch(); raw_left.right = Some(root); raw_left.fetch(); Some(left) } }; } fn rotate_left(root: &mut Link) { *root = { unsafe { let mut root = root.unwrap(); let mut right = root.as_ref().right.unwrap(); root.as_mut().right = right.as_mut().left; root.as_mut().fetch(); right.as_mut().left = Some(root); right.as_mut().fetch(); Some(right) } }; } if root.is_none() { return None; } let d = diff_height(root); if d > 1 { let left = &mut unsafe { root.unwrap().as_mut() }.left; if diff_height(*left) < 0 { rotate_left(left); } rotate_right(&mut root); } else if d < -1 { let right = &mut unsafe { root.unwrap().as_mut() }.right; if diff_height(*right) > 0 { rotate_right(right); } rotate_left(&mut root); } else { unsafe { root.unwrap().as_mut() }.fetch(); } root } fn merge_with_root(left: Link, root: Link, right: Link) -> Link { let d = height(left) - height(right); if d > 1 { let raw_left = unsafe { left.unwrap().as_mut() }; raw_left.right = merge_with_root(raw_left.right, root, right); balance(left) } else if d < -1 { let raw_right = unsafe { right.unwrap().as_mut() }; raw_right.left = merge_with_root(left, root, raw_right.left); balance(right) } else { let raw_root = unsafe { root.unwrap().as_mut() }; raw_root.left = left; raw_root.right = right; balance(root) } } fn merge(left: Link, right: Link) -> Link { fn remove_max(mut node: Link) -> (Link, Link) { let raw_node = unsafe { node.unwrap().as_mut() }; if raw_node.right.is_some() { let (tmp, removed) = remove_max(raw_node.right); raw_node.right = tmp; node = balance(node); (node, removed) } else { let removed = node; node = raw_node.left; (node, removed) } } if left.is_none() { right } else if right.is_none() { left } else { let (left, removed) = remove_max(left); merge_with_root(left, removed, right) } } fn split(root: Link, index: usize) -> (Link, Link) { if root.is_none() { return (None, None); } let (left, right) = { let raw_root = unsafe { root.unwrap().as_mut() }; let left = raw_root.left; let right = raw_root.right; raw_root.left = None; raw_root.right = None; (left, right) }; let left_len = len(left); if index < left_len { let tmp = split(left, index); (tmp.0, merge_with_root(tmp.1, root, right)) } else if index > left_len { let tmp = split(right, index - left_len - 1); (merge_with_root(left, root, tmp.0), tmp.1) } else { (left, merge_with_root(None, root, right)) } } fn get(root: Link, index: usize) -> Link { let raw_root = unsafe { root?.as_mut() }; let left = raw_root.left; let right = raw_root.right; let left_len = len(left); if index < left_len { get(left, index) } else if index > left_len { get(right, index - left_len - 1) } else { root } } fn bisect(root: Link, mut f: impl FnMut(&T) -> bool) -> usize { let node = if let Some(node) = root { unsafe { node.as_ref() } } else { return 0; }; let left = node.left; let right = node.right; let left_len = len(left); if !f(&node.value) { bisect(left, f) } else { bisect(right, f) + left_len + 1 } } #[allow(unused)] fn traverse( node: Link, mut preorder_f: impl FnMut(NodePtr), mut inorder_f: impl FnMut(NodePtr), mut postorder_f: impl FnMut(NodePtr), ) { fn dfs( node: Link, preorder_f: &mut impl FnMut(NodePtr), inorder_f: &mut impl FnMut(NodePtr), postorder_f: &mut impl FnMut(NodePtr), ) { if let Some(node) = node { let left = unsafe { node.as_ref() }.left; let right = unsafe { node.as_ref() }.right; preorder_f(node); dfs(left, preorder_f, inorder_f, postorder_f); inorder_f(node); dfs(right, preorder_f, inorder_f, postorder_f); postorder_f(node); } } dfs(node, &mut preorder_f, &mut inorder_f, &mut postorder_f); } #[allow(unused)] #[inline] fn traverse_preorder(node: Link, f: impl FnMut(NodePtr)) { traverse(node, f, |_| {}, |_| {}); } #[allow(unused)] #[inline] fn traverse_inorder(node: Link, f: impl FnMut(NodePtr)) { traverse(node, |_| {}, f, |_| {}); } #[allow(unused)] #[inline] fn traverse_postorder(node: Link, f: impl FnMut(NodePtr)) { traverse(node, |_| {}, |_| {}, f); } pub struct AvlTreeVec { root: Link, } impl AvlTreeVec { pub fn new() -> Self { Self::default() } pub fn clear(&mut self) { *self = Self::new(); } pub fn len(&self) -> usize { len(self.root) } pub fn is_empty(&self) -> bool { self.len() == 0 } pub fn get(&self, index: usize) -> Option<&T> { Some(&unsafe { get(self.root, index)?.as_ref() }.value) } pub fn get_mut(&mut self, index: usize) -> Option<&mut T> { Some(&mut unsafe { get(self.root, index)?.as_mut() }.value) } pub fn front(&self) -> Option<&T> { self.get(0) } pub fn back(&self) -> Option<&T> { self.get(self.len().checked_sub(1)?) } pub fn front_mut(&mut self) -> Option<&mut T> { self.get_mut(0) } pub fn back_mut(&mut self) -> Option<&mut T> { self.get_mut(self.len().checked_sub(1)?) } pub fn push_front(&mut self, value: T) { self.insert(0, value); } pub fn push_back(&mut self, value: T) { self.insert(self.len(), value); } pub fn pop_front(&mut self) -> Option { self.remove(0) } pub fn pop_back(&mut self) -> Option { self.remove(self.len().checked_sub(1)?) } pub fn insert(&mut self, index: usize, value: T) { assert!(index <= self.len()); let new_node = Some(Node::new(value)); let (left, right) = split(self.root.take(), index); self.root = merge_with_root(left, new_node, right); } pub fn remove(&mut self, index: usize) -> Option { (index < self.len()).then(|| { let (left, right) = split(self.root.take(), index); let (removed, right) = split(right, 1); self.root = merge(left, right); let boxed = unsafe { Box::from_raw(removed.unwrap().as_ptr()) }; boxed.value }) } pub fn append(&mut self, other: &mut Self) { self.root = merge(self.root.take(), other.root.take()) } pub fn split_off(&mut self, index: usize) -> Self { assert!(index <= self.len()); let (left, right) = split(self.root.take(), index); self.root = left; Self { root: right } } pub fn bisect(&self, f: impl FnMut(&T) -> bool) -> usize { bisect(self.root, f) } pub fn lower_bound(&self, value: &T) -> usize where T: Ord, { self.lower_bound_by(|e| e.cmp(value)) } pub fn lower_bound_by(&self, mut f: impl FnMut(&T) -> Ordering) -> usize { self.bisect(|e| f(e) == Ordering::Less) } pub fn lower_bound_by_key( &self, k: &K, mut f: impl FnMut(&T) -> K, ) -> usize { self.lower_bound_by(|e| f(e).cmp(k)) } pub fn upper_bound(&self, value: &T) -> usize where T: Ord, { self.upper_bound_by(|e| e.cmp(value)) } pub fn upper_bound_by(&self, mut f: impl FnMut(&T) -> Ordering) -> usize { self.bisect(|e| f(e) != Ordering::Greater) } pub fn upper_bound_by_key( &self, k: &K, mut f: impl FnMut(&T) -> K, ) -> usize { self.upper_bound_by(|x| f(x).cmp(k)) } pub fn iter(&self) -> Iter<'_, T> { Iter::new(self.root) } pub fn iter_mut(&mut self) -> IterMut<'_, T> { IterMut::new(self.root) } } impl Default for AvlTreeVec { fn default() -> Self { Self { root: None } } } impl Drop for AvlTreeVec { fn drop(&mut self) { traverse_postorder(self.root, |node| free(node)); } } impl Index for AvlTreeVec { type Output = T; fn index(&self, index: usize) -> &Self::Output { self.get(index).unwrap() } } impl IndexMut for AvlTreeVec { fn index_mut(&mut self, index: usize) -> &mut Self::Output { self.get_mut(index).unwrap() } } impl<'a, T> IntoIterator for &'a AvlTreeVec { type IntoIter = Iter<'a, T>; type Item = &'a T; fn into_iter(self) -> Self::IntoIter { self.iter() } } impl<'a, T> IntoIterator for &'a mut AvlTreeVec { type IntoIter = IterMut<'a, T>; type Item = &'a mut T; fn into_iter(self) -> Self::IntoIter { self.iter_mut() } } impl IntoIterator for AvlTreeVec { type IntoIter = IntoIter; type Item = T; fn into_iter(mut self) -> Self::IntoIter { IntoIter::new(self.root.take()) } } impl PartialEq for AvlTreeVec { fn eq(&self, other: &Self) -> bool { self.iter().eq(other.iter()) } } impl Eq for AvlTreeVec {} impl PartialOrd for AvlTreeVec { fn partial_cmp(&self, other: &Self) -> Option { self.iter().partial_cmp(other.iter()) } } impl Ord for AvlTreeVec { fn cmp(&self, other: &Self) -> Ordering { self.iter().cmp(other.iter()) } } impl Hash for AvlTreeVec { fn hash(&self, state: &mut H) { self.iter().for_each(|item| item.hash(state)); } } impl Extend for AvlTreeVec { fn extend>(&mut self, iter: I) { iter.into_iter().for_each(|item| { self.push_back(item); }); } } impl<'a, T: 'a + Copy> Extend<&'a T> for AvlTreeVec { fn extend>(&mut self, iter: I) { self.extend(iter.into_iter().cloned()); } } impl FromIterator for AvlTreeVec { fn from_iter>(iter: I) -> Self { let mut res = Self::new(); res.extend(iter); res } } impl From> for AvlTreeVec { fn from(v: Vec) -> Self { Self::from_iter(v) } } impl From<[T; N]> for AvlTreeVec { fn from(v: [T; N]) -> Self { Self::from_iter(v) } } impl Clone for AvlTreeVec { fn clone(&self) -> Self { Self::from_iter(self.iter().cloned()) } } impl Debug for AvlTreeVec { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { f.debug_list().entries(self.iter()).finish() } } struct IterBase<'a, T> { stack: Vec>, stack_rev: Vec>, phantom: PhantomData<&'a ()>, } impl<'a, T> IterBase<'a, T> { fn new(root: Link) -> Self { let mut iter = Self { stack: vec![], stack_rev: vec![], phantom: PhantomData::default(), }; iter.push_left(root); iter.push_right(root); iter } fn push_left(&mut self, mut node: Link) { while let Some(n) = node { self.stack.push(n); node = unsafe { n.as_ref() }.left; } } fn push_right(&mut self, mut node: Link) { while let Some(n) = node { self.stack_rev.push(n); node = unsafe { n.as_ref() }.right; } } fn next(&mut self) -> Option> { let node = self.stack.pop()?; self.push_left(unsafe { node.as_ref() }.right); Some(node) } fn next_back(&mut self) -> Option> { let node = self.stack_rev.pop()?; self.push_right(unsafe { node.as_ref() }.left); Some(node) } } pub struct Iter<'a, T>(IterBase<'a, T>); impl<'a, T: 'a> Iter<'a, T> { fn new(root: Link) -> Self { Self(IterBase::new(root)) } } impl<'a, T: 'a> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option { self.0.next().map(|node| &unsafe { node.as_ref() }.value) } } impl<'a, T: 'a> DoubleEndedIterator for Iter<'a, T> { fn next_back(&mut self) -> Option { self.0 .next_back() .map(|node| &unsafe { node.as_ref() }.value) } } pub struct IterMut<'a, T>(IterBase<'a, T>); impl<'a, T: 'a> IterMut<'a, T> { fn new(root: Link) -> Self { Self(IterBase::new(root)) } } impl<'a, T: 'a> Iterator for IterMut<'a, T> { type Item = &'a mut T; fn next(&mut self) -> Option { self.0 .next() .map(|mut node| &mut unsafe { node.as_mut() }.value) } } impl<'a, T: 'a> DoubleEndedIterator for IterMut<'a, T> { fn next_back(&mut self) -> Option { self.0 .next_back() .map(|mut node| &mut unsafe { node.as_mut() }.value) } } pub struct IntoIter { iter: std::vec::IntoIter, } impl IntoIter { fn new(root: Link) -> Self { let mut stack = Vec::with_capacity(len(root)); traverse_inorder(root, |node| { let boxed = unsafe { Box::from_raw(node.as_ptr()) }; stack.push(boxed.value) }); IntoIter { iter: stack.into_iter(), } } } impl Iterator for IntoIter { type Item = T; fn next(&mut self) -> Option { self.iter.next() } } impl DoubleEndedIterator for IntoIter { fn next_back(&mut self) -> Option { self.iter.next_back() } } } } }