結果
問題 |
No.649 ここでちょっとQK!
|
ユーザー |
![]() |
提出日時 | 2025-03-16 23:47:08 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 250 ms / 3,000 ms |
コード長 | 30,114 bytes |
コンパイル時間 | 17,182 ms |
コンパイル使用メモリ | 401,976 KB |
実行使用メモリ | 15,616 KB |
最終ジャッジ日時 | 2025-03-16 23:47:32 |
合計ジャッジ時間 | 20,517 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
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<T> { vec: AvlTreeVec<T>, } impl<T> AvlTreeMultiSet<T> { 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<T> { 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<T> Default for AvlTreeMultiSet<T> { fn default() -> Self { Self { vec: AvlTreeVec::default(), } } } impl<T> Index<usize> for AvlTreeMultiSet<T> { type Output = T; fn index(&self, index: usize) -> &Self::Output { self.nth(index).unwrap() } } impl<'a, T> IntoIterator for &'a AvlTreeMultiSet<T> { type IntoIter = Iter<'a, T>; type Item = &'a T; fn into_iter(self) -> Self::IntoIter { self.iter() } } impl<T> IntoIterator for AvlTreeMultiSet<T> { type IntoIter = IntoIter<T>; type Item = T; fn into_iter(self) -> Self::IntoIter { self.vec.into_iter() } } impl<T: PartialEq> PartialEq for AvlTreeMultiSet<T> { fn eq(&self, other: &Self) -> bool { self.iter().eq(other.iter()) } } impl<T: Eq> Eq for AvlTreeMultiSet<T> {} impl<T: PartialOrd> PartialOrd for AvlTreeMultiSet<T> { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { self.iter().partial_cmp(other.iter()) } } impl<T: Ord> Ord for AvlTreeMultiSet<T> { fn cmp(&self, other: &Self) -> Ordering { self.iter().cmp(other.iter()) } } impl<T: Hash> Hash for AvlTreeMultiSet<T> { fn hash<H: std::hash::Hasher>(&self, state: &mut H) { self.iter().for_each(|item| item.hash(state)); } } impl<T: Ord> Extend<T> for AvlTreeMultiSet<T> { fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { iter.into_iter().for_each(|x| { self.insert(x); }); } } impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for AvlTreeMultiSet<T> { fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { self.extend(iter.into_iter().cloned()); } } impl<T: Ord> FromIterator<T> for AvlTreeMultiSet<T> { fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { let mut res = Self::new(); res.extend(iter); res } } impl<T: Ord> From<Vec<T>> for AvlTreeMultiSet<T> { fn from(v: Vec<T>) -> Self { Self::from_iter(v) } } impl<T: Ord, const N: usize> From<[T; N]> for AvlTreeMultiSet<T> { fn from(v: [T; N]) -> Self { Self::from_iter(v) } } impl<T: Clone> Clone for AvlTreeMultiSet<T> { fn clone(&self) -> Self { Self { vec: self.vec.clone(), } } } impl<T: Debug> Debug for AvlTreeMultiSet<T> { 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<T> { value: T, len: usize, height: i32, left: Link<T>, right: Link<T>, } type NodePtr<T> = NonNull<Node<T>>; type Link<T> = Option<NodePtr<T>>; impl<T> Node<T> { fn new(value: T) -> NodePtr<T> { 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<T>(node: NodePtr<T>) { unsafe { drop(Box::from_raw(node.as_ptr())) }; } #[inline] fn len<T>(node: Link<T>) -> usize { node.map_or(0, |node| unsafe { node.as_ref() }.len) } #[inline] fn height<T>(node: Link<T>) -> i32 { node.map_or(0, |node| unsafe { node.as_ref() }.height) } #[inline] fn diff_height<T>(node: Link<T>) -> i32 { node.map_or(0, |node| { let node = unsafe { node.as_ref() }; height(node.left) - height(node.right) }) } fn balance<T>(mut root: Link<T>) -> Link<T> { fn rotate_right<T>(root: &mut Link<T>) { *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<T>(root: &mut Link<T>) { *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<T>(left: Link<T>, root: Link<T>, right: Link<T>) -> Link<T> { 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<T>(left: Link<T>, right: Link<T>) -> Link<T> { fn remove_max<T>(mut node: Link<T>) -> (Link<T>, Link<T>) { 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<T>(root: Link<T>, index: usize) -> (Link<T>, Link<T>) { 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<T>(root: Link<T>, index: usize) -> Link<T> { 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<T>(root: Link<T>, 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<T>( node: Link<T>, mut preorder_f: impl FnMut(NodePtr<T>), mut inorder_f: impl FnMut(NodePtr<T>), mut postorder_f: impl FnMut(NodePtr<T>), ) { fn dfs<T>( node: Link<T>, preorder_f: &mut impl FnMut(NodePtr<T>), inorder_f: &mut impl FnMut(NodePtr<T>), postorder_f: &mut impl FnMut(NodePtr<T>), ) { 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<T>(node: Link<T>, f: impl FnMut(NodePtr<T>)) { traverse(node, f, |_| {}, |_| {}); } #[allow(unused)] #[inline] fn traverse_inorder<T>(node: Link<T>, f: impl FnMut(NodePtr<T>)) { traverse(node, |_| {}, f, |_| {}); } #[allow(unused)] #[inline] fn traverse_postorder<T>(node: Link<T>, f: impl FnMut(NodePtr<T>)) { traverse(node, |_| {}, |_| {}, f); } pub struct AvlTreeVec<T> { root: Link<T>, } impl<T> AvlTreeVec<T> { 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<T> { self.remove(0) } pub fn pop_back(&mut self) -> Option<T> { 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<T> { (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<K: Ord>( &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<K: Ord>( &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<T> Default for AvlTreeVec<T> { fn default() -> Self { Self { root: None } } } impl<T> Drop for AvlTreeVec<T> { fn drop(&mut self) { traverse_postorder(self.root, |node| free(node)); } } impl<T> Index<usize> for AvlTreeVec<T> { type Output = T; fn index(&self, index: usize) -> &Self::Output { self.get(index).unwrap() } } impl<T> IndexMut<usize> for AvlTreeVec<T> { fn index_mut(&mut self, index: usize) -> &mut Self::Output { self.get_mut(index).unwrap() } } impl<'a, T> IntoIterator for &'a AvlTreeVec<T> { 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<T> { type IntoIter = IterMut<'a, T>; type Item = &'a mut T; fn into_iter(self) -> Self::IntoIter { self.iter_mut() } } impl<T> IntoIterator for AvlTreeVec<T> { type IntoIter = IntoIter<T>; type Item = T; fn into_iter(mut self) -> Self::IntoIter { IntoIter::new(self.root.take()) } } impl<T: PartialEq> PartialEq for AvlTreeVec<T> { fn eq(&self, other: &Self) -> bool { self.iter().eq(other.iter()) } } impl<T: Eq> Eq for AvlTreeVec<T> {} impl<T: PartialOrd> PartialOrd for AvlTreeVec<T> { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { self.iter().partial_cmp(other.iter()) } } impl<T: Ord> Ord for AvlTreeVec<T> { fn cmp(&self, other: &Self) -> Ordering { self.iter().cmp(other.iter()) } } impl<T: Hash> Hash for AvlTreeVec<T> { fn hash<H: std::hash::Hasher>(&self, state: &mut H) { self.iter().for_each(|item| item.hash(state)); } } impl<T> Extend<T> for AvlTreeVec<T> { fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { iter.into_iter().for_each(|item| { self.push_back(item); }); } } impl<'a, T: 'a + Copy> Extend<&'a T> for AvlTreeVec<T> { fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { self.extend(iter.into_iter().cloned()); } } impl<T> FromIterator<T> for AvlTreeVec<T> { fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { let mut res = Self::new(); res.extend(iter); res } } impl<T> From<Vec<T>> for AvlTreeVec<T> { fn from(v: Vec<T>) -> Self { Self::from_iter(v) } } impl<T, const N: usize> From<[T; N]> for AvlTreeVec<T> { fn from(v: [T; N]) -> Self { Self::from_iter(v) } } impl<T: Clone> Clone for AvlTreeVec<T> { fn clone(&self) -> Self { Self::from_iter(self.iter().cloned()) } } impl<T: Debug> Debug for AvlTreeVec<T> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { f.debug_list().entries(self.iter()).finish() } } struct IterBase<'a, T> { stack: Vec<NodePtr<T>>, stack_rev: Vec<NodePtr<T>>, phantom: PhantomData<&'a ()>, } impl<'a, T> IterBase<'a, T> { fn new(root: Link<T>) -> 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<T>) { while let Some(n) = node { self.stack.push(n); node = unsafe { n.as_ref() }.left; } } fn push_right(&mut self, mut node: Link<T>) { while let Some(n) = node { self.stack_rev.push(n); node = unsafe { n.as_ref() }.right; } } fn next(&mut self) -> Option<NodePtr<T>> { let node = self.stack.pop()?; self.push_left(unsafe { node.as_ref() }.right); Some(node) } fn next_back(&mut self) -> Option<NodePtr<T>> { 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<T>) -> Self { Self(IterBase::new(root)) } } impl<'a, T: 'a> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option<Self::Item> { 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::Item> { 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<T>) -> 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::Item> { 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::Item> { self.0 .next_back() .map(|mut node| &mut unsafe { node.as_mut() }.value) } } pub struct IntoIter<T> { iter: std::vec::IntoIter<T>, } impl<T> IntoIter<T> { fn new(root: Link<T>) -> 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<T> Iterator for IntoIter<T> { type Item = T; fn next(&mut self) -> Option<Self::Item> { self.iter.next() } } impl<T> DoubleEndedIterator for IntoIter<T> { fn next_back(&mut self) -> Option<Self::Item> { self.iter.next_back() } } } } }