結果

問題 No.649 ここでちょっとQK！
コンテスト
ユーザー ziita
提出日時 2020-09-12 19:34:28
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 700 ms / 3,000 ms
コード長 7,871 bytes
コンパイル時間 15,062 ms
コンパイル使用メモリ 400,692 KB
実行使用メモリ 22,824 KB
最終ジャッジ日時 2025-01-02 13:36:17
合計ジャッジ時間 27,111 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_imports)]
#![allow(non_snake_case, unused)]

use std::cmp::*;
use std::collections::*;
use std::ops::*;

// https://atcoder.jp/contests/hokudai-hitachi2019-1/submissions/10518254 より

macro_rules! eprint {
    ($($t:tt)*) => {{
        use ::std::io::Write;
        let _ = write!(::std::io::stderr(), $($t)*);
    }};
}
macro_rules! eprintln {
    () => { eprintln!(""); };
    ($($t:tt)*) => {{
        use ::std::io::Write;
        let _ = writeln!(::std::io::stderr(), $($t)*);
    }};
}
macro_rules! dbg {
    ($v:expr) => {{
        let val = $v;
        eprintln!("[{}:{}] {} = {:?}", file!(), line!(), stringify!($v), val);
        val
    }}
}

macro_rules! mat {
    ($($e:expr),*) => { Vec::from(vec![$($e),*]) };
    ($($e:expr,)*) => { Vec::from(vec![$($e),*]) };
    ($e:expr; $d:expr) => { Vec::from(vec![$e; $d]) };
    ($e:expr; $d:expr $(; $ds:expr)+) => { Vec::from(vec![mat![$e $(; $ds)*]; $d]) };
}

macro_rules! ok {
    ($a:ident$([$i:expr])*.$f:ident()$(@$t:ident)*) => {
        $a$([$i])*.$f($($t),*)
    };
    ($a:ident$([$i:expr])*.$f:ident($e:expr$(,$es:expr)*)$(@$t:ident)*) => { {
        let t = $e;
        ok!($a$([$i])*.$f($($es),*)$(@$t)*@t)
    } };
}

pub fn readln() -> String {
    let mut line = String::new();
    ::std::io::stdin().read_line(&mut line).unwrap_or_else(|e| panic!("{}", e));
    line
}

macro_rules! read {
    ($($t:tt),*; $n:expr) => {{
        let stdin = ::std::io::stdin();
        let ret = ::std::io::BufRead::lines(stdin.lock()).take($n).map(|line| {
            let line = line.unwrap();
            let mut it = line.split_whitespace();
            _read!(it; $($t),*)
        }).collect::<Vec<_>>();
        ret
    }};
    ($($t:tt),*) => {{
        let line = readln();
        let mut it = line.split_whitespace();
        _read!(it; $($t),*)
    }};
}

macro_rules! _read {
    ($it:ident; [char]) => {
        _read!($it; String).chars().collect::<Vec<_>>()
    };
    ($it:ident; [u8]) => {
        Vec::from(_read!($it; String).into_bytes())
    };
    ($it:ident; usize1) => {
        $it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1
    };
    ($it:ident; [usize1]) => {
        $it.map(|s| s.parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::<Vec<_>>()
    };
    ($it:ident; [$t:ty]) => {
        $it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::<Vec<_>>()
    };
    ($it:ident; $t:ty) => {
        $it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<$t>().unwrap_or_else(|e| panic!("{}", e))
    };
    ($it:ident; $($t:tt),+) => {
        ($(_read!($it; $t)),*)
    };
}


pub fn main() {
    let _ = ::std::thread::Builder::new().name("run".to_string()).stack_size(32 * 1024 * 1024).spawn(run).unwrap().join();
}

const MOD: i64 = 998244353;
// const MOD: usize = 1_000_000_007;
const INF: i64 = std::i64::MAX/2;

// https://www.slideshare.net/iwiwi/2-12188757

use std::cell::RefCell;
use std::rc::Rc;

type Ref = Rc<RefCell<Node>>;
type Link = Option<Ref>;

pub struct Node {
    val: i64,
    cnt: usize,
    sum: i64,
    pri: usize,
    left: Link,
    right: Link,
}

impl Node{
    pub fn new(val: i64, pri: usize) -> Self {
        Node {
            val: val,
            cnt: 1,
            sum: val,
            pri: pri,
            left: None,
            right: None,
        }
    }
}

fn update(x: Link) {
    if x.is_none() {
        return;
    }
    let t = x.unwrap();
    t.borrow_mut().cnt = 1;
    let mut tmp = t.borrow().val;
    t.borrow_mut().sum = tmp;
    if t.borrow().left.is_some() {
        let tmp = count(t.borrow().left.clone());
        t.borrow_mut().cnt += tmp;
        let tmp = sum(t.borrow().left.clone());
        t.borrow_mut().sum += tmp;
    }
    if t.borrow().right.is_some() {
        let tmp = count(t.borrow().right.clone());
        t.borrow_mut().cnt += tmp;
        let tmp = sum(t.borrow().left.clone());
        t.borrow_mut().sum += tmp;
    }
}

fn count(x: Link) -> usize {
    if x.is_none() {
        return 0;
    }
    x.unwrap().borrow().cnt
}

fn sum(x: Link) -> i64 {
    if x.is_none() {
        return 0;
    }
    x.unwrap().borrow().sum
}

fn merge(l: Link, r: Link) -> Link {
    if l.is_none() {
        return r;
    }
    else if r.is_none() {
        return l;
    }
    let ol = l.clone();
    let or = r.clone();
    let mut l_node = l.unwrap();
    let mut r_node = r.unwrap();
    if l_node.borrow().pri > r_node.borrow().pri {
        let tmp = merge(l_node.borrow().right.clone(), or);
        l_node.borrow_mut().right = tmp;
        update(Some(l_node.clone()));
        return ol;
    }
    else {
        let tmp = merge(ol,r_node.borrow().left.clone());
        r_node.borrow_mut().left = tmp;
        update(Some(r_node.clone()));
        return or;
    }
}

// [0,k), [k,n)
fn split(x: Link, k: usize) -> (Link,Link){
    if x.is_none() {
        return (None,None);
    }
    let t = x.unwrap();
    let left_count = count(t.borrow().left.clone());
    if k <= left_count {
        let (l,r) = split(t.borrow_mut().left.clone(), k);
        t.borrow_mut().left = r;
        update(Some(t.clone()));
        return (l,Some(t));
    }
    else {
        let (l,r) = split(t.borrow_mut().right.clone(), k-left_count-1);
        t.borrow_mut().right = l;
        update(Some(t.clone()));
        return (Some(t), r);
    }
}

pub fn insert(x: Link, k: usize, val: i64, pri: usize) -> Link {
    let node = Rc::new(RefCell::new(Node::new(val,pri)));
    if x.is_none() {
        return Some(node);
    }
    let (l,r) = split(x.clone(),k);
    let a = merge(l.clone(),Some(node));
    let b = merge(a,r.clone());
    b
}

// (erased Node, remaining Nodes)
pub fn erase(x: Link, k: usize) -> (Link,Link) {
    if x.is_none() {
        return (None,None);
    }
    if k==0 {
        return split(x.clone(), 1);
    }
    let (l,tmp) = split(x.clone(), k);
    let (ans,r) = split(tmp.clone(), 1);
    let res = merge(l.clone(),r.clone());
    (ans,res)
}

pub fn find_insert_point(x: Link, val: i64 , mut sum: &mut usize){
    if x.is_none() {
        return;
    }
    let t = x.unwrap();
    let lcnt = count(t.borrow().left.clone());
    if val <= t.borrow().val {
        find_insert_point(t.borrow_mut().left.clone(),val, &mut sum);
    }
    else {
        *sum += lcnt + 1;
        find_insert_point(t.borrow_mut().right.clone(),val, &mut sum);
    } 
}

pub fn push(x: Link, val: i64, pri: usize) -> Link {
    let mut sum = 0;
    find_insert_point(x.clone(),val,&mut sum);
    insert(x.clone(),sum,val,pri)
}

pub struct XorShift {
	pub x: [u32; 4]
}

impl XorShift {
	pub fn new(mut seed: u32) -> XorShift {
		let mut x = [0; 4];
		for i in 0..4 {
			seed = 1812433253u32.wrapping_mul(seed ^ (seed >> 30)).wrapping_add(i as u32);
			x[i] = seed;
		}
		XorShift { x: x }
	}
	pub fn next32(&mut self) -> usize {
		let t = self.x[0] ^ (self.x[0] << 11);
		for i in 0..3 { self.x[i] = self.x[i + 1] }
		self.x[3] = self.x[3] ^ (self.x[3] >> 19) ^ t ^ (t >> 8);
		self.x[3] as usize
	}
	/// [0, n)
	pub fn next(&mut self, n: usize) -> usize {
		loop {
			let t = self.next32();
			let r = t % n;
			if (t - r).checked_add(n).is_some() {
				return r;
			}
		}
	}
}

fn solve() {
    let (q,k) = read!(usize,usize);
    let query = read!([i64];q);
    let mut node: Link = None;
    let mut rng = XorShift::new(583290);
    for a in query {
        if a[0]==1 {
            node = push(node.clone(), a[1], rng.next(1000000));
        }
        else {
            if count(node.clone())<k {
                println!("-1");
            }
            else {
                let (ans,res) = erase(node.clone(), k-1);
                node = res;
                println!("{}",ans.unwrap().borrow().val);
            }
        }
    }
    
}

fn run() {
    solve();
}
0