#1013051 (Rust) No.649 ここでちょっとQK！

• 問題: No.649 ここでちょっとQK！
• ユーザー: CoCo_Japan_pan
• 提出日時: 2024-09-23 18:17:06
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 271 ms / 3,000 ms
• コード長: 8,143 bytes
• コンパイル時間: 12,067 ms
• コンパイル使用メモリ: 405,864 KB
• 実行使用メモリ: 15,488 KB
• 最終ジャッジ日時: 2024-09-24 06:47:19
• 合計ジャッジ時間: 17,588 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,812 KB
testcase_01	AC	1 ms; 6,816 KB
testcase_02	AC	1 ms; 6,948 KB
testcase_03	AC	7 ms; 6,940 KB
testcase_04	AC	100 ms; 15,360 KB
testcase_05	AC	103 ms; 15,360 KB
testcase_06	AC	101 ms; 15,488 KB
testcase_07	AC	1 ms; 6,940 KB
testcase_08	AC	1 ms; 6,940 KB
testcase_09	AC	1 ms; 6,944 KB
testcase_10	AC	1 ms; 6,944 KB
testcase_11	AC	1 ms; 6,944 KB
testcase_12	AC	108 ms; 7,552 KB
testcase_13	AC	109 ms; 7,424 KB
testcase_14	AC	108 ms; 7,168 KB
testcase_15	AC	114 ms; 7,552 KB
testcase_16	AC	111 ms; 7,936 KB
testcase_17	AC	128 ms; 8,192 KB
testcase_18	AC	141 ms; 8,960 KB
testcase_19	AC	156 ms; 9,472 KB
testcase_20	AC	170 ms; 9,984 KB
testcase_21	AC	186 ms; 10,496 KB
testcase_22	AC	202 ms; 11,136 KB
testcase_23	AC	220 ms; 11,776 KB
testcase_24	AC	236 ms; 12,288 KB
testcase_25	AC	254 ms; 12,800 KB
testcase_26	AC	271 ms; 13,312 KB
testcase_27	AC	1 ms; 6,940 KB
testcase_28	AC	1 ms; 6,944 KB
testcase_29	AC	2 ms; 6,940 KB
testcase_30	AC	102 ms; 6,940 KB
testcase_31	AC	105 ms; 6,940 KB
testcase_32	AC	1 ms; 6,940 KB
testcase_33	AC	1 ms; 6,944 KB
testcase_34	AC	1 ms; 6,940 KB
testcase_35	AC	1 ms; 6,940 KB

ソースコード

// verification-helper: PROBLEM https://yukicoder.me/problems/no/649
pub use __cargo_equip::prelude::*;

use avl::AVL;
use std::io::prelude::*;

fn main() {
    let stdin = std::io::read_to_string(std::io::stdin()).unwrap();
    let mut stdin = stdin.split_whitespace();
    let mut writer = std::io::BufWriter::new(std::io::stdout().lock());
    let q = stdin.next().unwrap().parse::<usize>().unwrap();
    let k = stdin.next().unwrap().parse::<usize>().unwrap();
    let mut multiset = AVL::new(true);
    for _ in 0..q {
        let t = stdin.next().unwrap().parse::<u8>().unwrap();
        if t == 1 {
            let v = stdin.next().unwrap().parse::<u64>().unwrap();
            multiset.insert(v);
        } else {
            if multiset.len() < k {
                writeln!(&mut writer, "-1").unwrap();
            } else {
                let ans = multiset.erase_index(k - 1).unwrap();
                writeln!(&mut writer, "{}", ans).unwrap();
            }
        }
    }
}
// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `avl 0.1.0 (path+███████████████████████████████████████████████████████████████)` published in ssh://[e-mail]/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` 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>>>;#[derive(Debug)]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;}fn rotate_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;}if height(&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();}}#[allow(unused)]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();}}#[allow(unused)]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>(mut left: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;};if value<=&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),}}#[derive(Debug)]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,))}pub fn 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 {}
    }
}