結果
問題 | No.649 ここでちょっとQK! |
ユーザー | CoCo_Japan_pan |
提出日時 | 2024-09-23 17:58:30 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 279 ms / 3,000 ms |
コード長 | 7,711 bytes |
コンパイル時間 | 13,356 ms |
コンパイル使用メモリ | 401,904 KB |
実行使用メモリ | 15,616 KB |
最終ジャッジ日時 | 2024-09-24 06:47:37 |
合計ジャッジ時間 | 17,136 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
pub use __cargo_equip::prelude::*;use avl::AVL;use proconio::{fastout, input};#[fastout]fn main() {input! {q: usize,k: usize,}let mut set = AVL::new(true);for _ in 0..q {input! {t: u8,}if t == 1 {input! {v: u64,}set.insert(v);} else {if set.len() < k {println!("-1");} else {let ans = set.erase_index(k - 1).unwrap();println!("{}", ans);}}}}// The following code was expanded by `cargo-equip`./// # Bundled libraries////// - `avl 0.1.0 (path+███████████████████████████████████████████████████████████████)` published in **missing** licensed under **missing** as`crate::__cargo_equip::crates::avl`#[cfg_attr(any(), rustfmt::skip)]#[allow(unused)]mod __cargo_equip {pub(crate) mod crates {pub mod avl {use std::cmp::Ordering;use std::fmt::Display;use std::mem::swap;type Tree<T> =Option<Box<Node<T>>>;struct Node<T>{left:Tree<T>,right:Tree<T>,value:T,len:usize,height:u8,}impl<T>Node<T>{fn new(value:T)->Node<T>{Self{left:None,right:None,value,len:1,height:1,}}fn update(&mut self){self.len=len(&self.left)+len(&self.right)+1;self.height=height(&self.left).max(height(&self.right))+1;}fnrotate_right(&mut self){let mut x=self.left.take().unwrap();let b=x.right.take();swap(self,&mut x);x.left=b;x.update();self.right=Some(x);self.update();}fn rotate_left(&mut self){let mut x=self.right.take().unwrap();let b=x.left.take();swap(self,&mut x);x.right=b;x.update();self.left=Some(x);self.update();}fn balance(&mut self){if height(&self.left).abs_diff(height(&self.right))<=1{self.update();return;}ifheight(&self.left)>height(&self.right){let left_child=self.left.as_mut().unwrap();if height(&left_child.left)<height(&left_child.right){left_child.rotate_left();}self.rotate_right();}else{let right_child=self.right.as_mut().unwrap();if height(&right_child.left)>height(&right_child.right){right_child.rotate_right();}self.rotate_left();}}fn verify_balance(&self){if height(&self.left).abs_diff(height(&self.right))>1{panic!("height: {} {}",height(&self.left),height(&self.right));}if let Some(left)=&self.left{left.verify_balance();}if let Some(right)=&self.right{right.verify_balance();}}fn verify_height(&self){if self.left.is_none()&&self.right.is_none(){assert_eq!(self.height,1);return;}if let Some(left)=&self.left{left.verify_height();}if let Some(right)=&self.right{right.verify_height();}assert_eq!(self.height,1+height(&self.left).max(height(&self.right)),"{} vs height: {} {}",self.height,height(&self.left),height(&self.right));}fn list_sub(self,ret:&mut Vec<T>){if let Some(left)=self.left{left.list_sub(ret);}ret.push(self.value);if let Some(right)=self.right{right.list_sub(ret);}}}impl<T:Display>Display for Node<T>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{if let Some(left)=&self.left{write!(f,"{}",left)?;}write!(f,"{}, ",self.value)?;if let Some(right)=&self.right{write!(f,"{}",right)?;}Ok(())}}fn len<T>(tree:&Tree<T>)->usize{tree.as_ref().map_or(0,|t|t.len)}fn height<T>(tree:&Tree<T>)->u8{tree.as_ref().map_or(0,|t|t.height)}fn merge<T>(left:Tree<T>,right:Tree<T>)->Tree<T>{match(left.is_some(),right.is_some()){(true,true)=>{let(_,center,rhs)=split_delete(right.unwrap(),0);Some(merge_with_root(left,center,rhs))}(false,_)=>right,(_,false)=>left,}}fn merge_with_root<T>(mutleft:Tree<T>,mut center:Box<Node<T>>,mut right:Tree<T>,)->Box<Node<T>>{if height(&left).abs_diff(height(&right))<=1{center.left=left;center.right=right;center.update();center}else if height(&left)<height(&right){let mut root=right.take().unwrap();root.left=Some(merge_with_root(left,center,root.left.take()));root.balance();root}else{let mut root=left.take().unwrap();root.right=Some(merge_with_root(root.right.take(),center,right));root.balance();root}}fn split_delete<T>(mut root:Box<Node<T>>,index:usize)->(Tree<T>,Box<Node<T>>,Tree<T>){debug_assert!((0..root.len).contains(&index));let left=root.left.take();let right=root.right.take();let lsize=len(&left);match lsize.cmp(&index){Ordering::Equal=>(left,root,right),Ordering::Less=>{let mut ret=split_delete(right.unwrap(),index-lsize-1);ret.0=Some(merge_with_root(left,root,ret.0));ret}Ordering::Greater=>{let mut ret=split_delete(left.unwrap(),index);ret.2=Some(merge_with_root(ret.2,root,right));ret}}}fn split<T>(tree:Tree<T>,index:usize)->(Tree<T>,Tree<T>){let Some(root)=tree else{return(None,None);};if index==0{(None,Some(root))}else if root.len==index{(Some(root),None)}else{let(left,center,right)=split_delete(root,index);(left,Some(merge_with_root(None,center,right)))}}fn lower_bound<T:PartialOrd>(tree:&Tree<T>,value:&T)->usize{let Some(tree)=tree else{return 0;};ifvalue<=&tree.value{lower_bound(&tree.left,value)}else{len(&tree.left)+1+lower_bound(&tree.right,value)}}fn upper_bound<T:PartialOrd>(tree:&Tree<T>,value:&T)->usize{let Some(tree)=tree else{return 0;};if value>=&tree.value{len(&tree.left)+1+upper_bound(&tree.right,value)}else{upper_bound(&tree.left,value)}}fn count<T:PartialOrd>(tree:&Tree<T>,value:&T)->usize{upper_bound(tree,value)-lower_bound(tree,value)}fn get<T>(tree:&Tree<T>,index:usize)->Option<&T>{if len(tree)<=index{return None;}let Some(tree)=tree else{return None;};let left_len=len(&tree.left);match index.cmp(&left_len){Ordering::Less=>get(&tree.left,index),Ordering::Equal=>Some(&tree.value),Ordering::Greater=>get(&tree.right,index-left_len-1),}}pub struct AVL<T>{root:Tree<T>,multi:bool,}impl<T:Display>Display for AVL<T>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{if let Some(root)=&self.root{write!(f,"{}",root)}else{write!(f,"Empty")}}}impl<T>AVL<T>{pub fn new(multi:bool)->Self{Self{root:None,multi}}pub fn len(&self)->usize{len(&self.root)}pub fn height(&self)->u8{height(&self.root)}pub fn is_empty(&self)->bool{self.root.is_none()}pub fn lower_bound(&self,value:&T)->usize where T:PartialOrd,{lower_bound(&self.root,value)}pub fn upper_bound(&self,value:&T)->usize where T:PartialOrd,{upper_bound(&self.root,value)}pub fn get(&self,index:usize)->Option<&T>{get(&self.root,index)}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,multi:self.multi}}pub fn insert_by_index(&mut self,index:usize,value:T){assert!(index<=self.len());let other=self.split_off(index);self.root=Some(merge_with_root(self.root.take(),Box::new(Node::new(value)),other.root,))}pubfn insert(&mut self,value:T)where T:PartialOrd,{if!self.multi{if self.count(&value)>0{return;}}let index=self.lower_bound(&value);self.insert_by_index(index,value);}pub fn erase_index(&mut self,index:usize)->Option<T>{if index<self.len(){let(left,center,right)=split_delete(self.root.take().unwrap(),index);self.root=merge(left,right);Some(center.value)}else{None}}pub fn erase(&mut self,value:&T)->bool where T:PartialOrd,{if self.count(value)==0{return false;}let index=self.lower_bound(value);let ret=self.erase_index(index);ret.is_some()}pub fn count(&self,value:&T)->usize where T:PartialOrd,{count(&self.root,value)}pub fn into_vec(self)->Vec<T>{let mut ret=Vec::with_capacity(self.len());if let Some(root)=self.root{root.list_sub(&mut ret);}ret}}}}pub(crate) mod macros {pub mod avl {}}pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}mod preludes {pub mod avl {}}}