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

提出ソース

結果

問題	No.649 ここでちょっとQK！
ユーザー	sakikuroe
提出日時	2022-08-13 10:30:30
言語	Rust (1.77.0)
結果	AC
実行時間	373 ms / 3,000 ms
コード長	8,314 bytes
コンパイル時間	692 ms
コンパイル使用メモリ	176,556 KB
実行使用メモリ	11,812 KB
最終ジャッジ日時	2023-10-24 19:57:51
合計ジャッジ時間	6,710 ms
ジャッジサーバーID （参考情報）	judge11 / judge14

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,348 KB
testcase_01	AC	1 ms 4,348 KB
testcase_02	AC	1 ms 4,348 KB
testcase_03	AC	270 ms 4,348 KB
testcase_04	AC	51 ms 11,812 KB
testcase_05	AC	53 ms 11,360 KB
testcase_06	AC	50 ms 11,360 KB
testcase_07	AC	1 ms 4,348 KB
testcase_08	AC	1 ms 4,348 KB
testcase_09	AC	1 ms 4,348 KB
testcase_10	AC	1 ms 4,348 KB
testcase_11	AC	1 ms 4,348 KB
testcase_12	AC	150 ms 6,208 KB
testcase_13	AC	148 ms 6,208 KB
testcase_14	AC	147 ms 6,192 KB
testcase_15	AC	155 ms 6,212 KB
testcase_16	AC	155 ms 6,208 KB
testcase_17	AC	176 ms 6,628 KB
testcase_18	AC	198 ms 7,052 KB
testcase_19	AC	218 ms 7,460 KB
testcase_20	AC	242 ms 7,892 KB
testcase_21	AC	265 ms 8,312 KB
testcase_22	AC	289 ms 8,736 KB
testcase_23	AC	308 ms 9,160 KB
testcase_24	AC	319 ms 9,584 KB
testcase_25	AC	344 ms 10,004 KB
testcase_26	AC	373 ms 10,420 KB
testcase_27	AC	2 ms 4,348 KB
testcase_28	AC	1 ms 4,348 KB
testcase_29	AC	2 ms 4,348 KB
testcase_30	AC	146 ms 6,204 KB
testcase_31	AC	156 ms 6,200 KB
testcase_32	AC	1 ms 4,348 KB
testcase_33	AC	1 ms 4,348 KB
testcase_34	AC	1 ms 4,348 KB
testcase_35	AC	1 ms 4,348 KB

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

コンパイルメッセージ

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

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

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

warning: variable does not need to be mutable
   --> Main.rs:173:13
    |
173 |         let mut root = self as *mut SplayNode;
    |             ----^^^^
    |             |
    |             help: remove this `mut`

warning: variable does not need to be mutable
   --> Main.rs:196:13
    |
196 |         let mut root = self as *mut SplayNode;
    |             ----^^^^
    |             |
    |             help: remove this `mut`

warning: variable does not need to be mutable
   --> Main.rs:203:38
    |
203 | fn merge(mut l_root: *mut SplayNode, mut r_root: *mut SplayNode) -> *mut SplayNode {
    |                                      ----^^^^^^
    |                                      |
    |                                      help: remove this `mut`

warning: variable does not need to be mutable
   --> Main.rs:228:13
    |
228 |         let mut l_root = (*root).left;
    |             ----^^^^^^
    |             |
    |             help: remove this `mut`

warning: variable does not need to be mutable
   --> Main.rs:229:13
    |
229 |         let mut r_root = root;
    |             ----^^^^^^
    |             |
    |             help: remove this `mut`

warning: variable does not need to be mutable
   --> Main.rs:240:13
    |
240 |         let mut l_root = (*root).left;
    |             ----^^^^^^
    |

ソースコード

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 {
    key: isize,
    left: *mut Self,
    right: *mut Self,
    parent: *mut Self,
    size: usize,
}

impl SplayNode {
    fn new(key: isize) -> 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(&mut self, mut idx: usize) -> *mut SplayNode {
        let mut root = self as *mut SplayNode;
        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: isize) -> usize {
        let mut root = self as *mut SplayNode;
        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 insert(&mut self, node: *mut SplayNode) -> *mut SplayNode {
        let mut root = self as *mut SplayNode;
        let idx = unsafe { (*root).lower_bound((*node).key) };
        let (l_root, r_root) = split(root, idx);
        merge(merge(l_root, node), r_root)
    }
}

fn merge(mut l_root: *mut SplayNode, mut r_root: *mut SplayNode) -> *mut SplayNode {
    unsafe {
        if l_root.is_null() {
            r_root
        } else if r_root.is_null() {
            l_root
        } else {
            l_root = (*l_root).get((*l_root).size - 1);
            (*l_root).right = r_root;
            (*r_root).parent = l_root;
            (*l_root).update();
            l_root
        }
    }
}

fn split(mut root: *mut SplayNode, idx: usize) -> (*mut SplayNode, *mut SplayNode) {
    unsafe {
        if idx == 0 {
            return (null_mut(), root);
        }
        if idx == (*root).size {
            return (root, null_mut());
        }
        root = (*root).get(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 remove(mut root: *mut SplayNode, idx: usize) -> (*mut SplayNode, *mut SplayNode) {
    unsafe {
        root = (*root).get(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)
    }
}

pub struct SplayBST {
    root: *mut SplayNode,
}

impl SplayBST {
    fn new() -> Self {
        SplayBST { root: null_mut() }
    }

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

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

    fn remove(&mut self, x: isize) {
        unsafe {
            let idx = (*(*self).root).lower_bound(x);
            self.root = remove((*self).root, 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(k - 1) {
                println!("{}", v);
                bst.remove(v);
            } else {
                println!("-1");
            }
        }
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード