結果

問題 No.649 ここでちょっとQK！
ユーザー sakikuroesakikuroe
提出日時 2022-08-13 08:45:42
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 370 ms / 3,000 ms
コード長 7,940 bytes
コンパイル時間 19,956 ms
コンパイル使用メモリ 403,004 KB
実行使用メモリ 11,776 KB
最終ジャッジ日時 2024-09-24 12:14:51
合計ジャッジ時間 21,343 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,812 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 261 ms
6,812 KB
testcase_04 AC 53 ms
11,776 KB
testcase_05 AC 55 ms
11,264 KB
testcase_06 AC 53 ms
11,264 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 153 ms
6,940 KB
testcase_13 AC 151 ms
6,944 KB
testcase_14 AC 151 ms
6,944 KB
testcase_15 AC 160 ms
6,944 KB
testcase_16 AC 159 ms
6,944 KB
testcase_17 AC 177 ms
6,944 KB
testcase_18 AC 196 ms
6,940 KB
testcase_19 AC 223 ms
7,296 KB
testcase_20 AC 240 ms
7,936 KB
testcase_21 AC 259 ms
8,192 KB
testcase_22 AC 278 ms
8,704 KB
testcase_23 AC 303 ms
9,088 KB
testcase_24 AC 325 ms
9,472 KB
testcase_25 AC 346 ms
9,856 KB
testcase_26 AC 370 ms
10,240 KB
testcase_27 AC 2 ms
6,940 KB
testcase_28 AC 2 ms
6,940 KB
testcase_29 AC 2 ms
6,944 KB
testcase_30 AC 147 ms
6,944 KB
testcase_31 AC 154 ms
6,940 KB
testcase_32 AC 1 ms
6,944 KB
testcase_33 AC 1 ms
6,940 KB
testcase_34 AC 1 ms
6,940 KB
testcase_35 AC 1 ms
6,940 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: variable does not need to be mutable
  --> src/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
  --> src/main.rs:82:17
   |
82 |             let mut pp = (*p).parent;
   |                 ----^^
   |                 |
   |                 help: remove this `mut`

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

warning: variable does not need to be mutable
   --> src/main.rs:172:38
    |
172 | 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
   --> src/main.rs:197:13
    |
197 |         let mut l_root = (*root).left;
    |             ----^^^^^^
    |             |
    |             help: remove this `mut`

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

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

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

ソースコード

diff # 

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 root: *mut SplayNode, mut idx: usize) -> *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 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 = get(l_root, (*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 = get(root, 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 = get(root, 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 lower_bound(root: *mut SplayNode, x: isize) -> usize {
    unsafe {
        if x <= (*root).key {
            if (*root).left.is_null() {
                return 0;
            } else {
                lower_bound((*root).left, x)
            }
        } else {
            (if (*root).left.is_null() {
                0
            } else {
                (*(*root).left).size
            }) + if (*root).right.is_null() {
                0
            } else {
                lower_bound((*root).right, x)
            } + 1
        }
    }
}

fn insert(root: *mut SplayNode, node: *mut SplayNode) -> *mut SplayNode {
    let idx = unsafe { lower_bound(root, (*node).key) };
    let (l_root, r_root) = split(root, idx);
    merge(merge(l_root, node), r_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 {
            self.root = insert((*self).root, 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 = get(self.root, idx);
        unsafe {
            if self.root.is_null() {
                None
            } else {
                Some((*self.root).key)
            }
        }
    }

    fn remove(&mut self, x: isize) {
        let idx = lower_bound((*self).root, 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");
            }
        }
    }
}
0