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

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