Submission #1212481
Source Code Expand
fn main() {
let mut cin = cin();
while cin.read() {
let mut res = String::new();
let q = cin.next();
let mut rbst = None;
for _ in 0..q {
match cin.next() {
1 => {
let x = cin.next();
rbst = Node::<i32>::insert(rbst, x);
},
2 => {
let x:usize = cin.next();
let a = Node::at(&rbst, x-1).unwrap();
use std::fmt::Write;
writeln!(&mut res, "{}", a).unwrap();
rbst = Node::erase_one(rbst, a);
},
_ => {
panic!();
}
}
}
print!("{}", res);
}
}
#[allow(dead_code)]
fn cin() -> Scanner<std::io::Stdin> {
Scanner::new(std::io::stdin())
}
#[allow(dead_code)]
pub struct Scanner<T> {
buf: Vec<u8>,
len: usize,
idx: usize,
next: Option<String>,
reader: T,
}
#[allow(dead_code)]
impl<Reader: std::io::Read> Scanner<Reader> {
fn new(r: Reader) -> Scanner<Reader> {
Scanner {
buf: vec![0; 8192],
len: 0,
idx: 0,
next: None,
reader: r,
}
}
fn next<T: std::str::FromStr>(&mut self) -> T {
self.wrapped::<T>().unwrap()
}
fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.next()).collect()
}
fn mat<T: std::str::FromStr>(&mut self, r: usize, c: usize) -> Vec<Vec<T>> {
(0..r).map(|_| self.vec(c)).collect()
}
fn vec_char(&mut self) -> Vec<char> {
self.read();
self.next.take().unwrap().chars().collect()
}
fn mat_char(&mut self, r: usize) -> Vec<Vec<char>> {
(0..r).map(|_| self.vec_char()).collect()
}
fn wrapped<T: std::str::FromStr>(&mut self) -> Option<T> {
self.read();
self.next.take().and_then(|s| s.parse::<T>().ok())
}
fn read(&mut self) -> bool {
if self.next.is_some() {
return true;
}
let mut s = String::with_capacity(16);
while let Some(c) = self.get_char() {
if !c.is_whitespace() {
s.push(c);
} else if !s.is_empty() {
break;
}
}
self.next = if !s.is_empty() { Some(s) } else { None };
self.next.is_some()
}
fn get_char(&mut self) -> Option<char> {
if self.idx == self.len {
match self.reader.read(&mut self.buf[..]) {
Ok(l) if l > 0 => {
self.idx = 0;
self.len = l;
}
_ => return None,
}
}
self.idx += 1;
Some(self.buf[self.idx - 1] as char)
}
}
struct Node<T: std::cmp::PartialOrd + Copy> {
val: T,
size: usize,
left: Option<Box<Node<T>>>,
right: Option<Box<Node<T>>>
}
type Link<T> = Option<Box<Node<T>>>;
impl<T: std::cmp::PartialOrd + Copy> Node<T> {
fn singleton(val: T) -> Node<T> {
Node {
val: val,
size: 1,
left: None,
right: None,
}
}
pub fn update(&mut self) {
self.size = Self::size(&self.left) + Self::size(&self.right) + 1;
}
pub fn insert(n: Link<T>, new_val: T) -> Link<T> {
let (left, right) = Self::split_less(n, new_val);
let single = Some(Box::new(Node::singleton(new_val)));
let n = Self::merge(left, single);
Self::merge(n, right)
}
pub fn erase_all(n: Link<T>, val: T) -> Link<T> {
let (left, right) = Self::split_less(n, val);
let (_, right) = Self::split_leq(right, val);
Self::merge(left, right)
}
pub fn erase_one(n: Link<T>, val: T) -> Link<T> {
let (left, right) = Self::split_less(n, val);
let (_, right) = Self::split_at(right, 1);
Self::merge(left, right)
}
fn merge(left: Link<T>, right: Link<T>) -> Link<T> {
match (left, right) {
(None, r) => r,
(l, None) => l,
(mut l, mut r) => {
let mut l = l.take().unwrap();
let mut r = r.take().unwrap();
if rand() as usize % (l.size + r.size) < l.size {
let lr = (*l).right.take();
l.right = Self::merge(lr, Some(r));
l.update();
Some(l)
} else {
let rl = (*r).left.take();
r.left = Self::merge(Some(l), rl);
r.update();
Some(r)
}
}
}
}
fn split_less(n: Link<T>, val: T) -> (Link<T>, Link<T>) {
Self::split_cmp_impl(n, &|n: &Box<Node<T>>| n.val < val)
}
fn split_leq(n: Link<T>, val: T) -> (Link<T>, Link<T>) {
Self::split_cmp_impl(n, &|n: &Box<Node<T>>| n.val <= val)
}
fn split_cmp_impl(n: Link<T>, f: &Fn(&Box<Node<T>>) -> bool) -> (Link<T>, Link<T>) {
match n {
None => (None, None),
Some(mut n) => {
if f(&n) {
let (l, r) = Self::split_cmp_impl(n.right.take(), f);
n.right = l;
n.update();
(Some(n), r)
} else {
let (l, r) = Self::split_cmp_impl(n.left.take(), f);
n.left = r;
n.update();
(l, Some(n))
}
}
}
}
fn split_at(n: Link<T>, k: usize) -> (Link<T>, Link<T>) {
match n {
None => (None, None),
Some(mut n) => {
let ls = Self::size(&n.left);
if k <= ls {
let nl = n.left.take();
let (l, r) = Self::split_at(nl, k);
n.left = r;
n.update();
(l, Some(n))
} else {
let nr = n.right.take();
let (l, r) = Self::split_at(nr, k - ls - 1);
n.right = l;
n.update();
(Some(n), r)
}
}
}
}
fn size(n: &Link<T>) -> usize {
match n {
&None => 0,
&Some(ref n) => n.size,
}
}
fn at(n: &Link<T>, k: usize) -> Option<T> {
match n {
&None => None,
&Some(ref n) => {
let ls = Node::size(&n.left);
if k < ls {
Self::at(&n.left, k)
} else if k == ls {
Some(n.val)
} else {
Self::at(&n.right, k - ls - 1)
}
}
}
}
}
static mut RAND_X: u32 = 123456789;
static mut RAND_Y: u32 = 987654321;
static mut RAND_Z: u32 = 1000000007;
static mut RAND_W: u32 = 1145141919;
fn rand() -> u32 {
unsafe {
let t = RAND_X ^ (RAND_X << 11);
RAND_X = RAND_Y;
RAND_Y = RAND_Z;
RAND_Z = RAND_W;
RAND_W = (RAND_W ^ (RAND_W >> 19)) ^ (t ^ (t >> 8));
RAND_W
}
}
Submission Info
Submission Time |
|
Task |
C - データ構造 |
User |
tubo28 |
Language |
Rust (1.15.1) |
Score |
100 |
Code Size |
7528 Byte |
Status |
AC |
Exec Time |
295 ms |
Memory |
10492 KB |
Compile Error
warning: method is never used: `erase_all`, #[warn(dead_code)] on by default
--> ./Main.rs:142:5
|
142 | pub fn erase_all(n: Link<T>, val: T) -> Link<T> {
| _____^ starting here...
143 | | let (left, right) = Self::split_less(n, val);
144 | | let (_, right) = Self::split_leq(right, val);
145 | | Self::merge(left, right)
146 | | }
| |_____^ ...ending here
warning: method is never used: `split_leq`, #[warn(dead_code)] on by default
--> ./Main.rs:180:5
|
180 | fn split_leq(n: Link<T>, val: T) -> (Link<T>, Link<T>) {
| _____^ starting here...
181 | | Self::split_cmp_impl(n, &|n: &Box<Node<T>>| n.val <= val)
182 | | }
| |_____^ ...ending here
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
All |
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
2 ms |
4352 KB |
sample_02.txt |
AC |
2 ms |
4352 KB |
subtask1_01.txt |
AC |
2 ms |
4352 KB |
subtask1_02.txt |
AC |
2 ms |
4352 KB |
subtask1_03.txt |
AC |
2 ms |
4352 KB |
subtask1_04.txt |
AC |
8 ms |
4352 KB |
subtask1_05.txt |
AC |
18 ms |
4352 KB |
subtask1_06.txt |
AC |
2 ms |
4352 KB |
subtask1_07.txt |
AC |
154 ms |
6524 KB |
subtask1_08.txt |
AC |
129 ms |
4988 KB |
subtask1_09.txt |
AC |
118 ms |
4988 KB |
subtask1_10.txt |
AC |
269 ms |
6652 KB |
subtask1_11.txt |
AC |
269 ms |
6652 KB |
subtask1_12.txt |
AC |
295 ms |
10492 KB |
subtask1_13.txt |
AC |
275 ms |
8444 KB |
subtask1_14.txt |
AC |
274 ms |
8444 KB |
subtask1_15.txt |
AC |
105 ms |
6396 KB |
subtask1_16.txt |
AC |
180 ms |
6652 KB |