結果
| 問題 |
No.649 ここでちょっとQK！
|
| コンテスト | |
| ユーザー |
 sakikuroe
|
| 提出日時 | 2022-08-13 10:49:09 |
| 言語 | Rust (1.83.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 32 |
コンパイルメッセージ
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`
ソースコード
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");
}
}
}
}