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

提出ソース

結果

問題	No.649 ここでちょっとQK！
ユーザー	sakikuroe
提出日時	2022-08-13 10:49:09
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	344 ms / 3,000 ms
コード長	8,722 bytes
コンパイル時間	19,100 ms
コンパイル使用メモリ	405,136 KB
実行使用メモリ	11,776 KB
最終ジャッジ日時	2024-09-24 15:05:44
合計ジャッジ時間	17,254 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	1 ms 6,812 KB
testcase_02	AC	1 ms 6,944 KB
testcase_03	AC	240 ms 6,940 KB
testcase_04	AC	51 ms 11,776 KB
testcase_05	AC	53 ms 11,392 KB
testcase_06	AC	49 ms 11,264 KB
testcase_07	AC	1 ms 6,944 KB
testcase_08	AC	0 ms 6,944 KB
testcase_09	AC	1 ms 6,944 KB
testcase_10	AC	1 ms 6,940 KB
testcase_11	AC	1 ms 6,940 KB
testcase_12	AC	141 ms 6,940 KB
testcase_13	AC	141 ms 6,944 KB
testcase_14	AC	140 ms 6,940 KB
testcase_15	AC	148 ms 6,940 KB
testcase_16	AC	153 ms 6,944 KB
testcase_17	AC	170 ms 6,944 KB
testcase_18	AC	186 ms 7,040 KB
testcase_19	AC	210 ms 7,296 KB
testcase_20	AC	227 ms 7,808 KB
testcase_21	AC	241 ms 8,192 KB
testcase_22	AC	260 ms 8,704 KB
testcase_23	AC	289 ms 9,088 KB
testcase_24	AC	295 ms 9,344 KB
testcase_25	AC	318 ms 9,856 KB
testcase_26	AC	344 ms 10,240 KB
testcase_27	AC	1 ms 6,940 KB
testcase_28	AC	2 ms 6,940 KB
testcase_29	AC	2 ms 6,944 KB
testcase_30	AC	139 ms 6,944 KB
testcase_31	AC	143 ms 6,944 KB
testcase_32	AC	1 ms 6,944 KB
testcase_33	AC	1 ms 6,940 KB
testcase_34	AC	1 ms 6,944 KB
testcase_35	AC	1 ms 6,944 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: variable does not need to be mutable
  --> src/main.rs:87:17
   |
87 |             let mut p = self.parent;
   |                 ----^
   |                 |
   |                 help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

warning: variable does not need to be mutable
  --> src/main.rs:88:17
   |
88 |             let mut pp = (*p).parent;
   |                 ----^^
   |                 |
   |                 help: remove this `mut`

warning: variable does not need to be mutable
  --> src/main.rs:89:17
   |
89 |             let mut c;
   |                 ----^
   |                 |
   |                 help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:211:17
    |
211 |             let mut l_root = (*root).left;
    |                 ----^^^^^^
    |                 |
    |                 help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:212:17
    |
212 |             let mut r_root = root;
    |                 ----^^^^^^
    |                 |
    |                 help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:231:17
    |
231 |             let mut l_root = (*root).left;
    |                 ----^^^^^^
    |                 |
    |                 help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:232:17
    |
232 |             let mut r_root = (*root).right;
    |                 ----^^^^^^
    |                 |
    |                 help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:248:44
    |
248 | fn merge<T>(mut l_root: *mut SplayNode<T>, mut r_root: *mut SplayNode<T>) -> *mut SplayNode<T>
    |                                            ----^^^^^^
    |                                            |
    |                                            help: remove this `mut`

ソースコード

raw source code

use std::{
    cmp::Ordering,
    ptr::{self, null_mut},
};

macro_rules! read_line {
    ($($xs: tt)*) => {
        let mut buf = String::new();
        std::io::stdin().read_line(&mut buf).unwrap();
        let mut iter = buf.split_whitespace();
        expand!(iter, $($xs)*);
    };
}

macro_rules! expand {
    ($iter: expr,) => {};
    ($iter: expr, mut $var: ident : $type: tt, $($xs: tt)*) => {
        let mut $var = value!($iter, $type);
        expand!($iter, $($xs)*);
    };
    ($iter: expr, $var: ident : $type: tt, $($xs: tt)*) => {
        let $var = value!($iter, $type);
        expand!($iter, $($xs)*);
    };
}

macro_rules! value {
    ($iter:expr, ($($type: tt),*)) => {
        ($(value!($iter, $type)),*);
    };
    ($iter: expr, [$type: tt; $len: expr]) => {
        (0..$len).map(|_| value!($iter, $type)).collect::<Vec<_>>()
    };
    ($iter: expr, Chars) => {
        value!($iter, String).chars().collect::<Vec<_>>>()
    };
    ($iter: expr, $type: ty) => {
        if let Some(v) = $iter.next() {
            v.parse::<$type>().ok()
        } else {
            None
        }
    };
}

#[derive(Clone, PartialEq, Eq)]
struct SplayNode<T>
where
    T: Ord + Copy,
{
    key: T,
    left: *mut Self,
    right: *mut Self,
    parent: *mut Self,
    size: usize,
}

impl<T> SplayNode<T>
where
    T: Ord + Copy,
{
    fn new(key: T) -> Self {
        SplayNode {
            key,
            left: null_mut(),
            right: null_mut(),
            parent: null_mut(),
            size: 1,
        }
    }

    fn update(&mut self) {
        unsafe {
            self.size = 1;
            if !self.left.is_null() {
                self.size += (*(self.left)).size;
            }

            if !self.right.is_null() {
                self.size += (*(self.right)).size;
            }
        }
    }

    fn rotate(&mut self) {
        unsafe {
            let mut p = self.parent;
            let mut pp = (*p).parent;
            let mut c;

            if (*p).left == self {
                c = self.right;
                self.right = p;
                (*p).left = c;
            } else {
                c = self.left;
                self.left = p;
                (*p).right = c;
            }

            if !pp.is_null() {
                if (*pp).left == p {
                    (*pp).left = self;
                }
                if (*pp).right == p {
                    (*pp).right = self;
                }
            }

            self.parent = pp;
            (*p).parent = self;
            if !c.is_null() {
                (*c).parent = p;
            }

            (*p).update();
            self.update();
        }
    }

    fn state(&self) -> isize {
        unsafe {
            if !self.parent.is_null() && ptr::eq((*self.parent).left, self) {
                1
            } else if !self.parent.is_null() && ptr::eq((*self.parent).right, self) {
                -1
            } else {
                0
            }
        }
    }

    fn splay(&mut self) {
        unsafe {
            while !self.parent.is_null() {
                if (*self.parent).state() == 0 {
                    // zig
                    self.rotate();
                } else if (*self).state() == (*self.parent).state() {
                    // zig-zag
                    (*self.parent).rotate();
                    (*self).rotate();
                } else {
                    // zig-zig
                    (*self).rotate();
                    (*self).rotate();
                }
            }
        }
    }

    fn get_nth(&mut self, mut idx: usize) -> *mut SplayNode<T> {
        let mut root = self as *mut SplayNode<T>;
        unsafe {
            loop {
                let lsize = if !(*root).left.is_null() {
                    (*(*root).left).size
                } else {
                    0
                };
                match idx.cmp(&lsize) {
                    Ordering::Less => {
                        root = (*root).left;
                    }
                    Ordering::Equal => {
                        (*root).splay();
                        return root;
                    }
                    Ordering::Greater => {
                        root = (*root).right;
                        idx = idx - lsize - 1;
                    }
                }
            }
        }
    }

    fn lower_bound(&mut self, x: T) -> usize {
        let root = self as *mut SplayNode<T>;
        unsafe {
            if x <= (*root).key {
                if (*root).left.is_null() {
                    return 0;
                } else {
                    (*(*root).left).lower_bound(x)
                }
            } else {
                (if (*root).left.is_null() {
                    0
                } else {
                    (*(*root).left).size
                }) + if (*root).right.is_null() {
                    0
                } else {
                    (*(*root).right).lower_bound(x)
                } + 1
            }
        }
    }

    fn split(&mut self, idx: usize) -> (*mut SplayNode<T>, *mut SplayNode<T>) {
        let mut root = self as *mut SplayNode<T>;
        unsafe {
            if idx == 0 {
                return (null_mut(), root);
            }
            if idx == (*root).size {
                return (root, null_mut());
            }
            root = (*root).get_nth(idx);
            let mut l_root = (*root).left;
            let mut r_root = root;
            (*r_root).left = null_mut();
            (*l_root).parent = null_mut();
            (*r_root).update();
            (l_root, r_root)
        }
    }

    fn insert(&mut self, node: *mut SplayNode<T>) -> *mut SplayNode<T> {
        let root = self as *mut SplayNode<T>;
        let idx = unsafe { (*root).lower_bound((*node).key) };
        let (l_root, r_root) = unsafe { (*root).split(idx) };
        merge(merge(l_root, node), r_root)
    }

    fn remove(&mut self, idx: usize) -> (*mut SplayNode<T>, *mut SplayNode<T>) {
        let mut root = self as *mut SplayNode<T>;
        unsafe {
            root = (*root).get_nth(idx);
            let mut l_root = (*root).left;
            let mut r_root = (*root).right;
            if !l_root.is_null() {
                (*l_root).parent = null_mut()
            };
            if !r_root.is_null() {
                (*r_root).parent = null_mut()
            };

            (*root).left = null_mut();
            (*root).right = null_mut();
            (*root).update();
            (merge(l_root, r_root), root)
        }
    }
}

fn merge<T>(mut l_root: *mut SplayNode<T>, mut r_root: *mut SplayNode<T>) -> *mut SplayNode<T>
where
    T: Ord + Copy,
{
    unsafe {
        if l_root.is_null() {
            r_root
        } else if r_root.is_null() {
            l_root
        } else {
            l_root = (*l_root).get_nth((*l_root).size - 1);
            (*l_root).right = r_root;
            (*r_root).parent = l_root;
            (*l_root).update();
            l_root
        }
    }
}

pub struct SplayBST<T>
where
    T: Ord + Copy,
{
    root: *mut SplayNode<T>,
}

impl<T> SplayBST<T>
where
    T: Ord + Copy,
{
    fn new() -> Self {
        SplayBST { root: null_mut() }
    }

    fn insert(&mut self, x: T) {
        let add = Box::into_raw(Box::new(SplayNode::new(x)));
        if (self.root as *mut SplayNode<T>).is_null() {
            self.root = add;
        } else {
            unsafe {
                self.root = (*(*self).root).insert(add);
            }
        }
    }

    fn get_nth(&mut self, idx: usize) -> Option<T> {
        unsafe {
            if (*self).root.is_null() {
                return None;
            }
            if (*(*self).root).size <= idx {
                return None;
            }
            self.root = (*self.root).get_nth(idx);
            if self.root.is_null() {
                None
            } else {
                Some((*self.root).key)
            }
        }
    }

    fn remove(&mut self, x: T) {
        unsafe {
            let idx = (*(*self).root).lower_bound(x);
            self.root = (*(*self).root).remove(idx).0;
        }
    }
}

fn main() {
    read_line! {
        q: usize, k: usize,
    }
    let (q, k) = (q.unwrap(), k.unwrap());

    let mut bst = SplayBST::new();

    for _ in 0..q {
        read_line! {
            t: usize, v: isize,
        }
        let t = t.unwrap();

        if t == 1 {
            let v = v.unwrap();
            bst.insert(v);
        } else {
            if let Some(v) = bst.get_nth(k - 1) {
                println!("{}", v);
                bst.remove(v);
            } else {
                println!("-1");
            }
        }
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード