Submission #1290335

---

Source Code Expand

macro_rules! p {
    ($a:expr) => {
        println!("{:.10}", $a);
    };
    ($a:expr, $($b:expr),+) => {
        print!("{:.10} ", $a);
        p!($($b),+);
    };
}

#[allow(dead_code)]
mod sgtree {
    use std;
    use std::cmp::Ordering::*;

    type Link<T> = Option<Box<Node<T>>>;

    pub struct SgTree<T> {
        pub root: Link<T>,
    }

    impl<T> SgTree<T> {
        pub fn new() -> Self {
            SgTree {
                root: None,
            }
        }

        pub fn at(&self, k: usize) -> Option<&T> {
            if let Some(n) = at(&self.root, k) {
                Some(&n.val)
            } else {
                None
            }
        }

        pub fn remove_at(&mut self, k: usize) -> bool {
            if remove_at(&mut self.root, k) {
                if self.should_rebuild() {
                    self.root = rebuild(self.root.take());
                }
                true
            } else {
                false
            }
        }

        fn should_rebuild(&self) -> bool {
            total_size(&self.root) > size(&self.root) * 2
        }
    }

    impl<T: std::fmt::Display> SgTree<T> {
        pub fn show(&self) {
            println!("===");
            dfs(&self.root, 0);
        }
    }

    impl<T: PartialOrd> SgTree<T> {
        pub fn insert(&mut self, val: T) {
            self.root = insert(self.root.take(), val);
        }

        pub fn remove(&mut self, val: &T) -> bool {
            if remove(&mut self.root, val) {
                if self.should_rebuild() {
                    self.root = rebuild(self.root.take());
                }
                true
            } else {
                false
            }
        }

        pub fn find(&self, val: &T) -> Option<&T> {
            if let Some(n) = find(&self.root, &val) {
                Some(&n.val)
            } else {
                None
            }
        }
    }

    pub struct Node<T> {
        val: T,
        left: Link<T>,
        right: Link<T>,
        size: usize,
        total_size: usize,
        height: usize,
        deleted: bool,
    }

    impl<T> Node<T> {
        fn new(val: T) -> Link<T> {
            Some(Box::new(Node {
                val: val,
                left: None,
                right: None,
                size: 1,
                total_size: 1,
                height: 1,
                deleted: false,
            }))
        }

        fn update(&mut self) {
            self.size = size(&self.left) + size(&self.right) + if self.deleted { 0 } else { 1 };
            self.total_size = total_size(&self.left) + total_size(&self.right) + 1;
            self.height = std::cmp::max(height(&self.left), height(&self.right)) + 1;
        }
    }

    // verified
    fn insert<T: PartialOrd>(n: Link<T>, val: T) -> Link<T> {
        match n {
            None => Node::new(val),
            Some(mut n) => {
                match val.partial_cmp(&n.val).unwrap() {
                    Less => n.left = insert(n.left.take(), val),
                    Equal => if n.deleted { n.deleted = false },
                    Greater => n.right = insert(n.right.take(), val),
                }
                n.update();
                if n.height as f64 > 3.0 * (n.total_size as f64).ln() {
                    rebuild(Some(n))
                } else {
                    Some(n)
                }
            }
        }
    }

    // verified
    fn find<'a, T: PartialOrd>(n: &'a Link<T>, val: &T) -> Option<&'a Node<T>> {
        match *n {
            None => None,
            Some(ref n) => {
                match val.partial_cmp(&n.val).unwrap() {
                    Less => find(&n.left, val),
                    Equal => if !n.deleted { Some(n) } else { None },
                    Greater => find(&n.right, val),
                }
            }
        }
    }

    // verified
    fn remove<T: PartialOrd>(n: &mut Link<T>, val: &T) -> bool {
        match *n {
            None => false,
            Some(ref mut n) => {
                let res = match val.partial_cmp(&n.val).unwrap() {
                    Less => remove(&mut n.left, val),
                    Equal => if !n.deleted { n.deleted = true; true } else { false },
                    Greater => remove(&mut n.right, val),
                };
                if res {
                    n.update()
                }
                res
            }
        }
    }

    // verified
    fn at<T>(n: &Link<T>, k: usize) -> Option<&Node<T>> {
        match *n {
            None => None,
            Some(ref n) => {
                let ls = size(&n.left);
                match k.cmp(&ls) {
                    Less => at(&n.left, k),
                    Equal if !n.deleted => Some(n),
                    _ => at(&n.right, k - if n.deleted { ls } else { ls + 1 }),
                }
            }
        }
    }

    // verified
    fn remove_at<T>(n: &mut Link<T>, k: usize) -> bool {
        match *n {
            None => false,
            Some(ref mut n) => {
                let ls = size(&n.left);
                let del = n.deleted;
                let res = match k.cmp(&ls) {
                    Less => remove_at(&mut n.left, k),
                    Equal if !del => { n.deleted = true; true },
                    _ => remove_at(&mut n.right, k - if del { ls } else { ls + 1 }),
                };
                if res {
                    n.update()
                }
                res
            }
        }
    }

    // verified
    fn rebuild<T>(n: Link<T>) -> Link<T> {
        let mut buf = Vec::with_capacity(size(&n));
        flatten(n, &mut buf);
        let len = buf.len();
        make_bst(&mut buf, 0, len)
    }

    // verified
    fn flatten<T>(n: Link<T>, buf: &mut Vec<Link<T>>) {
        match n {
            Some(mut n) => {
                let (l, r) = (n.left.take(), n.right.take());
                flatten(l, buf);
                if !n.deleted {
                    buf.push(Some(n));
                }
                flatten(r, buf);
            }
            _ => (),
        }
    }

    // verified
    fn make_bst<T>(buf: &mut Vec<Link<T>>, l: usize, r: usize) -> Link<T> {
        if l == r {
            None
        } else {
            let m = l + (r - l) / 2;
            let mut res = buf[m].take().unwrap();
            res.left = make_bst(buf, l, m);
            res.right = make_bst(buf, m + 1, r);
            res.update();
            Some(res)
        }
    }

    // verified
    #[inline(always)]
    fn size<T>(n: &Link<T>) -> usize {
        match *n {
            None => 0,
            Some(ref n) => n.size,
        }
    }

    #[inline(always)]
    fn total_size<T>(n: &Link<T>) -> usize {
        match *n {
            None => 0,
            Some(ref n) => n.total_size,
        }
    }

    // verified
    #[inline(always)]
    fn height<T>(n: &Link<T>) -> usize {
        match *n {
            None => 0,
            Some(ref n) => n.height,
        }
    }

    // verified
    pub fn dfs<T: std::fmt::Display>(n: &Link<T>, d: usize) {
        match *n {
            Some(ref n) => {
                dfs(&n.left, d + 1);
                for _ in 0..d {
                    print!("  ");
                }
                println!("{} : {} {} {}", n.val, n.deleted, n.size, n.total_size);
                dfs(&n.right, d + 1);
            }
            _ => (),
        }
    }
}

#[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)
    }
}

fn rand() -> u32 {
    static mut RAND_X: u32 = 123456789;
    static mut RAND_Y: u32 = 987654321;
    static mut RAND_Z: u32 = 1000000007;
    static mut RAND_W: u32 = 1145141919;
    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
    }
}

fn main() {
    use sgtree::*;
    let mut cin = cin();

    if false {
        let q = 1000;
        let mut queries = Vec::<(u32, u32)>::new();
        let mut s = Vec::new();
        for _ in 0..q {
            if s.len() == 0 || rand() % 2 == 0 {
                loop {
                    let x = rand() % 100;
                    match s.binary_search(&x) {
                        Err(k) => {
                            s.insert(k, x);
                            queries.push((1, x as u32));
                            break;
                        }
                        _ => (),
                    }
                }
            } else {
                let k = rand() % s.len() as u32;
                s.remove(k as usize);
                queries.push((2, k + 1));
            }
        }
        let mut t = SgTree::new();
        for &(ty, x) in queries.iter() {
            match ty {
                1 => {
                    p!("insert", x);
                    t.insert(x as u32);
                }
                2 => {
                    p!("remove", x);
                    let k = x as usize - 1;
                    {
                        let kth = t.at(k);
                        p!(kth.unwrap());
                    }
                    t.remove_at(k);
                }
                _ => {
                    panic!();
                }
            }
        }
    } else {
        while cin.read() {
            let mut res = String::new();
            let q = cin.next();
            let mut t = SgTree::<i32>::new();
            for _ in 0..q {
                match cin.next() {
                    1 => {
                        let x: i32 = cin.next();
                        t.insert(x);
                    }
                    2 => {
                        let k = cin.next::<usize>() - 1;
                        let kth = t.at(k).unwrap().clone();
                        use std::fmt::Write;
                        writeln!(&mut res, "{}", kth).unwrap();
                        t.remove(&kth);
                    }
                    _ => {
                        panic!();
                    }
                }
                // t.show();
            }
            print!("{}", res);
        }
    }
}

Submission Info

Judge Result