Submission #1293875
Source Code Expand
#[macro_use]
mod io {
use std::io::*;
pub trait Scan<T> {
fn scan<R: Read>(sc: &mut Scanner<R>) -> T;
}
macro_rules! scan_primitive {
($t: ty) => {
impl Scan<$t> for $t {
fn scan<R: Read>(sc: &mut Scanner<R>) -> $t {
sc.next_token().expect("EOF?").parse()
.unwrap_or_else(|e| panic!("Cannot parse {}", e))
}
}
};
($t: ty, $($u: ty),+) => {
scan_primitive!($t);
scan_primitive!($($u),+);
};
}
macro_rules! scan_tuple {
($($t: ident),*) => {
impl< $($t: Scan<$t>),* > Scan< ( $($t),* ) > for ( $($t),* ) {
fn scan<R: Read>(sc: &mut Scanner<R>) -> ( $($t),* ) {
( $( $t::scan(sc)),* )
}
}
};
}
scan_primitive!(u8, u16, u32, u64, i8, i16, i32, i64,
f32, f64, usize, isize, bool, String);
scan_tuple!(T, U);
scan_tuple!(T, U, V);
scan_tuple!(T, U, V, W);
#[allow(dead_code)]
pub fn cin() -> Scanner<Stdin> {
Scanner::new(stdin())
}
#[allow(dead_code)]
pub struct Scanner<T> {
buf: Vec<u8>,
len: usize,
idx: usize,
reader: T,
}
#[allow(dead_code)]
impl<Reader: Read> Scanner<Reader> {
pub fn new(r: Reader) -> Scanner<Reader> {
Scanner {
buf: vec![0; 8192],
len: 0,
idx: 0,
reader: r,
}
}
pub fn next<T: Scan<T>>(&mut self) -> T {
T::scan::<Reader>(self)
}
fn next_token(&mut self) -> Option<String> {
let mut res = String::with_capacity(16);
while let Some(c) = self.get_u8() {
let d = c as char;
if !d.is_whitespace() {
res.push(d);
} else if res.len() != 0 {
self.unget_u8(c);
break;
}
}
if res.len() == 0 { None } else { Some(res) }
}
pub fn next_line(&mut self) -> String {
self.next_line_wrapped().unwrap()
}
pub fn next_line_wrapped(&mut self) -> Option<String> {
let c = self.get_u8();
if c.is_none() {
return None;
}
let mut line = String::with_capacity(20);
line.push(c.unwrap() as char);
loop {
let c = self.get_u8();
if c.is_none() || c.unwrap() == b'\n' {
// コメントはC++等での仕様
// if c.is_some() {
// self.unget_u8(b'\n');
// }
return Some(line);
}
line.push(c.unwrap() as char);
}
}
pub fn has_next(&mut self) -> bool {
loop {
let c = self.get_u8();
if c.is_none() {
return false;
}
let c = c.unwrap();
if !(c as char).is_whitespace() {
self.unget_u8(c);
return true;
}
}
}
fn get_u8(&mut self) -> Option<u8> {
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])
}
fn unget_u8(&mut self, c: u8) {
self.idx = self.idx - 1;
self.buf[self.idx] = c;
}
}
// Output
macro_rules! dump {
($($a: expr),+) => {{
use std::io::*;
write!(stderr(), "{}:{}\t", file!(), line!()).unwrap();
dump!(A $($a),+);
write!(stderr(), " = ").unwrap();
dump!(B $($a),+);
writeln!(stderr(), "").unwrap();
}};
(A $x: expr) => {
write!(stderr(), "{}", stringify!($x)).unwrap();
};
(A $x: expr, $($y: expr),+) => {
write!(stderr(), "{}, ", stringify!($x)).unwrap();
dump!(A $($y),+);
};
(B $x: expr) => {
write!(stderr(), "{:#?}", $x).unwrap();
};
(B $x: expr, $($y: expr),+) => {
write!(stderr(), "{:#?}, ", $x).unwrap();
dump!(B $($y),+);
};
}
macro_rules! p {
($x:expr) => {
println!("{:.10}", $x);
};
($x:expr, $($y:expr),+) => {
print!("{:.10} ", $x);
p!($($y),+);
};
}
}
#[allow(unused_imports)]
use io::*;
#[allow(dead_code)]
mod avl_tree {
use std;
use std::cmp::Ordering::*;
use std::fmt::*;
type Link<T> = Option<Box<Node<T>>>;
pub struct AVLTree<T> {
pub root: Link<T>,
}
impl<T> AVLTree<T> {
pub fn new() -> Self {
AVLTree { 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) -> Option<T> {
let (root, kth) = remove_at(self.root.take(), k);
self.root = root;
kth
}
pub fn merge(&mut self, right: &mut AVLTree<T>) {
self.root = merge(self.root.take(), right.root.take());
}
pub fn split_at(&mut self, k: usize) -> (AVLTree<T>, AVLTree<T>) {
let (left, right) = split_at(self.root.take(), k);
(AVLTree { root: left }, AVLTree { root: right })
}
}
impl<T: PartialOrd> AVLTree<T> {
pub fn insert(&mut self, val: T) {
self.root = insert(self.root.take(), val);
}
pub fn remove(&mut self, val: &T) -> bool {
let (root, flg) = remove(self.root.take(), val);
self.root = root;
flg
}
pub fn find(&self, val: &T) -> Option<&T> {
if let Some(n) = find(&self.root, &val) {
Some(&n.val)
} else {
None
}
}
pub fn split(&mut self, val: &T) -> (AVLTree<T>, AVLTree<T>) {
let (left, right) = split(self.root.take(), val);
(AVLTree { root: left }, AVLTree { root: right })
}
// get the number of elements which is less than val
pub fn count_less(&mut self, val: &T) -> usize {
count_less(&self.root, &val)
}
}
impl<T: PartialOrd + Debug> AVLTree<T> {
pub fn check(&self) {
if let Some(ref root) = self.root {
debug_assert!(balance_factor(&self.root).abs() < 2);
root.verify();
}
}
}
#[derive(Debug)]
pub struct Node<T> {
left: Link<T>,
val: T,
right: Link<T>,
size: usize,
height: isize,
}
impl<T> Node<T> {
fn new(val: T) -> Link<T> {
Some(Box::new(Node {
val: val,
left: None,
right: None,
size: 1,
height: 1,
}))
}
#[inline(always)]
fn update(&mut self) {
self.size = size(&self.left) + size(&self.right) + 1;
self.height = std::cmp::max(height(&self.left), height(&self.right)) + 1;
}
}
impl<T: PartialOrd> Node<T> {
fn verify(&self) {
debug_assert_eq!(self.size, size(&self.left) + size(&self.right) + 1);
debug_assert_eq!(self.height,
std::cmp::max(height(&self.left), height(&self.right)) + 1);
debug_assert!(balance_factor(&self.left).abs() < 2);
match self.left {
Some(ref l) => {
debug_assert!(l.val < self.val);
l.verify();
}
_ => (),
}
debug_assert!(balance_factor(&self.right).abs() < 2);
match self.right {
Some(ref r) => {
debug_assert!(self.val < r.val);
r.verify();
}
_ => (),
}
}
}
// 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 => (), // TODO: optional
Greater => n.right = insert(n.right.take(), val),
}
n.update();
balance(Some(n))
}
}
}
// verified
fn remove<T: PartialOrd>(n: Link<T>, val: &T) -> (Link<T>, bool) {
match n {
None => (n, false),
Some(mut n) => {
match val.partial_cmp(&n.val).unwrap() {
Less => {
let (left, flg) = remove(n.left.take(), val);
n.left = left;
n.update();
(balance(Some(n)), flg)
}
Equal => {
let (q, r) = (n.left.take(), n.right.take());
match r {
None => (q, true),
Some(r) => {
let (r, mut min) = remove_leftmost(Some(r));
min.left = q;
min.right = r;
min.update();
(balance(Some(min)), true)
}
}
}
Greater => {
let (right, flg) = remove(n.right.take(), val);
n.right = right;
n.update();
(balance(Some(n)), flg)
}
}
}
}
}
// verified
// delete the leftmost (minimum) Node from n. returns (modified n, removed Node)
fn remove_leftmost<T>(n: Link<T>) -> (Link<T>, Box<Node<T>>) {
let mut n = n.unwrap();
match n.left {
None => {
let right = n.right.take();
n.update();
(right, n)
}
_ => {
let (left, min) = remove_leftmost(n.left.take());
n.left = left;
n.update();
(balance(Some(n)), min)
}
}
}
// (new n, deleted max)
// delete the rightmost (maximum) Node from n. returns (modified n, removed Node)
fn remove_rightmost<T>(n: Link<T>) -> (Link<T>, Box<Node<T>>) {
let mut n = n.unwrap();
match n.right {
None => {
let left = n.left.take();
n.update();
(left, n)
}
_ => {
let (right, max) = remove_rightmost(n.right.take());
n.right = right;
n.update();
(balance(Some(n)), max)
}
}
}
fn merge<T>(left: Link<T>, right: Link<T>) -> Link<T> {
match (left, right) {
(None, right) => right,
(left, None) => left,
(mut left, mut right) => {
if size(&left) > size(&right) {
let (right, x) = remove_leftmost(right.take());
merge_into_left(left, Some(x), right)
} else {
let (left, x) = remove_rightmost(left.take());
merge_into_right(left, Some(x), right)
}
}
}
}
// merge left, par, and right. size of par must be one.
fn merge3<T>(left: Link<T>, par: Link<T>, right: Link<T>) -> Link<T> {
debug_assert!(size(&par) == 1);
if size(&left) > size(&right) {
merge_into_left(left, par, right)
} else {
merge_into_right(left, par, right)
}
}
fn merge_into_left<T>(left: Link<T>, par: Link<T>, right: Link<T>) -> Link<T> {
debug_assert_eq!(size(&par), 1);
debug_assert!(size(&left) >= size(&right));
if height(&left) > height(&right) + 1 {
let mut left = left.unwrap();
left.right = merge_into_left(left.right.take(), par, right);
left.update();
balance(Some(left))
} else {
let mut par = par.unwrap();
par.left = left;
par.right = right;
par.update();
balance(Some(par))
}
}
fn merge_into_right<T>(left: Link<T>, par: Link<T>, right: Link<T>) -> Link<T> {
debug_assert_eq!(size(&par), 1);
debug_assert!(size(&left) <= size(&right));
if height(&left) + 1 < height(&right) {
let mut right = right.unwrap();
right.left = merge_into_right(left, par, right.left.take());
right.update();
balance(Some(right))
} else {
let mut par = par.unwrap();
par.left = left;
par.right = right;
par.update();
balance(Some(par))
}
}
fn split<T: PartialOrd>(n: Link<T>, val: &T) -> (Link<T>, Link<T>) {
match n {
None => (None, None),
Some(mut n) => {
let (l, r) = (n.left.take(), n.right.take());
n.update();
match val.partial_cmp(&n.val).unwrap() {
Less => {
let (ll, lr) = split(l, val);
(ll, merge3(lr, Some(n), r))
}
Equal => (l, merge(Some(n), r)),
Greater => {
let (rl, rr) = split(r, val);
(merge3(l, Some(n), rl), rr)
}
}
}
}
}
// verified
fn split_at<T>(n: Link<T>, k: usize) -> (Link<T>, Link<T>) {
debug_assert!(k <= size(&n));
match n {
None => (None, None),
Some(mut n) => {
let (l, r) = (n.left.take(), n.right.take());
n.update();
let sl = size(&l);
match k.cmp(&sl) {
Less => {
let (ll, lr) = split_at(l, k);
(ll, merge3(lr, Some(n), r))
}
Equal => (l, merge(Some(n), r)),
Greater => {
let (rl, rr) = split_at(r, k - sl - 1);
(merge3(l, Some(n), rl), rr)
}
}
}
}
}
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 => Some(n),
Greater => find(&n.right, val),
}
}
}
}
// 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 => Some(n),
Greater => at(&n.right, k - ls - 1),
}
}
}
}
// verified
fn remove_at<T>(n: Link<T>, k: usize) -> (Link<T>, Option<T>) {
match n {
None => (n, None),
Some(mut n) => {
match k.cmp(&size(&n.left)) {
Less => {
let (left, kth) = remove_at(n.left.take(), k);
n.left = left;
n.update();
(balance(Some(n)), kth)
}
Equal => {
let (q, r) = (n.left.take(), n.right.take());
match r {
None => (q, Some(n.val)),
Some(r) => {
let (r, mut min) = remove_leftmost(Some(r));
min.left = q;
min.right = r;
min.update();
(balance(Some(min)), Some(n.val))
}
}
}
Greater => {
let sl = size(&n.left);
let (right, kth) = remove_at(n.right.take(), k - sl - 1);
n.right = right;
n.update();
(balance(Some(n)), kth)
}
}
}
}
}
fn count_less<T: PartialOrd>(n: &Link<T>, val: &T) -> usize {
match *n {
None => 0,
Some(ref n) => {
let sl = size(&n.left);
match val.partial_cmp(&n.val).unwrap() {
Less => count_less(&n.left, val),
Equal => sl,
Greater => sl + 1 + count_less(&n.right, val),
}
}
}
}
// verified
fn balance<T>(n: Link<T>) -> Link<T> {
match balance_factor(&n) {
-1 | 0 | 1 => n,
2 => {
let mut n = n.unwrap();
if balance_factor(&n.right) < 0 {
n.right = rotate_right(n.right.take());
}
rotate_left(Some(n))
}
-2 => {
let mut n = n.unwrap();
if balance_factor(&n.left) > 0 {
n.left = rotate_left(n.left.take());
}
rotate_right(Some(n))
}
_ => panic!(),
}
}
// verified
#[inline(always)]
fn rotate_left<T>(q: Link<T>) -> Link<T> {
let mut q = q.unwrap();
let mut p = q.right.take().unwrap();
q.right = p.left.take();
q.update();
p.left = Some(q);
p.update();
Some(p)
}
// verified
#[inline(always)]
fn rotate_right<T>(p: Link<T>) -> Link<T> {
let mut p = p.unwrap();
let mut q = p.left.take().unwrap();
p.left = q.right.take();
p.update();
q.right = Some(p);
q.update();
Some(q)
}
// verified
#[inline(always)]
fn size<T>(n: &Link<T>) -> usize {
match *n {
None => 0,
Some(ref n) => n.size,
}
}
// verified
#[inline(always)]
fn height<T>(n: &Link<T>) -> isize {
match *n {
None => 0,
Some(ref n) => n.height,
}
}
// verified
#[inline(always)]
fn balance_factor<T>(n: &Link<T>) -> isize {
match *n {
None => panic!(),
Some(ref n) => height(&n.right) - height(&n.left),
}
}
// verified
pub fn insert_ms<T: PartialOrd>(n: Link<T>, x: T) -> Link<T> {
let (l, r) = split(n, &x);
merge3(l, Node::new(x), r)
}
// verified
pub fn remove_at_ms<T>(n: Link<T>, k: usize) -> (Link<T>, Option<T>) {
if k < size(&n) {
let (l, r) = split_at(n, k);
let (right, kth) = remove_leftmost(r);
(merge(l, right), Some(kth.val))
} else {
(n, None)
}
}
// verified
pub fn remove_ms<T: PartialOrd>(n: Link<T>, val: &T) -> (Link<T>, bool) {
if find(&n, &val).is_some() {
let (l, r) = split(n, val);
let (right, _) = remove_leftmost(r);
(merge(l, right), true)
} else {
(n, false)
}
}
}
fn main() {
use avl_tree::*;
use std::fmt::Write;
let mut sc = cin();
while sc.has_next() {
let mut res1 = String::new();
let mut res2 = String::new();
let q = sc.next();
let mut t = AVLTree::<i32>::new();
let mut u = AVLTree::<i32>::new();
for _ in 0..q {
match sc.next() {
1 => {
let x: i32 = sc.next();
t.insert(x);
u.root = insert_ms(u.root.take(), x);
},
2 => {
let k = sc.next::<usize>() - 1;
{
let kth = t.remove_at(k).unwrap().clone();
writeln!(&mut res1, "{}", kth).unwrap();
}
{
let (root, kth) = remove_at_ms(u.root.take(), k);
u.root = root;
writeln!(&mut res2, "{}", kth.unwrap()).unwrap();
}
},
_ => {
panic!();
}
}
}
assert!(res1 == res2);
print!("{}", res1);
}
}
Submission Info
Submission Time |
|
Task |
C - データ構造 |
User |
tubo28 |
Language |
Rust (1.15.1) |
Score |
100 |
Code Size |
22377 Byte |
Status |
AC |
Exec Time |
358 ms |
Memory |
22780 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
All |
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
2 ms |
4352 KB |
sample_02.txt |
AC |
2 ms |
4352 KB |
subtask1_01.txt |
AC |
2 ms |
4352 KB |
subtask1_02.txt |
AC |
2 ms |
4352 KB |
subtask1_03.txt |
AC |
2 ms |
4352 KB |
subtask1_04.txt |
AC |
9 ms |
4476 KB |
subtask1_05.txt |
AC |
22 ms |
4352 KB |
subtask1_06.txt |
AC |
2 ms |
4352 KB |
subtask1_07.txt |
AC |
183 ms |
10620 KB |
subtask1_08.txt |
AC |
156 ms |
7036 KB |
subtask1_09.txt |
AC |
143 ms |
7036 KB |
subtask1_10.txt |
AC |
319 ms |
14844 KB |
subtask1_11.txt |
AC |
319 ms |
14844 KB |
subtask1_12.txt |
AC |
358 ms |
22780 KB |
subtask1_13.txt |
AC |
337 ms |
16636 KB |
subtask1_14.txt |
AC |
340 ms |
16636 KB |
subtask1_15.txt |
AC |
223 ms |
12540 KB |
subtask1_16.txt |
AC |
254 ms |
14844 KB |