結果
| 問題 |
No.449 ゆきこーだーの雨と雪 (4)
|
| ユーザー |
 ngtkana
|
| 提出日時 | 2023-11-06 01:31:30 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 202 ms / 5,000 ms |
| コード長 | 29,589 bytes |
| コンパイル時間 | 22,301 ms |
| コンパイル使用メモリ | 380,456 KB |
| 実行使用メモリ | 18,172 KB |
| 最終ジャッジ日時 | 2024-09-25 22:57:04 |
| 合計ジャッジ時間 | 25,705 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 43 |
コンパイルメッセージ
warning: unused import: `map::Multimap`
--> src/main.rs:808:13
|
808 | pub use map::Multimap;
| ^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unused import: `map::Segmap`
--> src/main.rs:810:13
|
810 | pub use map::Segmap;
| ^^^^^^^^^^^
warning: unused import: `map::SegmapOp`
--> src/main.rs:811:13
|
811 | pub use map::SegmapOp;
| ^^^^^^^^^^^^^
ソースコード
use input::input;
use input::input_array;
use input::input_vec;
use std::cmp::Reverse;
use std::collections::HashMap;
fn main() {
let _ = input::<usize>();
let a = input_vec::<u64>();
let q = input::<usize>();
let queries = std::iter::repeat_with(|| {
let [name, p] = input_array::<String, 2>();
(name, p.parse::<char>().unwrap())
})
.take(q)
.collect::<Vec<_>>();
let mut name_id = HashMap::new();
for (name, _) in &queries {
let len = name_id.len();
name_id.entry(name).or_insert(len);
}
let n = name_id.len();
// (Reverse(score), time)
let mut map = rb::Multiset::new();
let mut keys = vec![(Reverse(0), 0); n];
let mut solved = vec![0; a.len()];
for i in 0..n {
map.insert(keys[i]);
}
let mut time = 0;
for &(ref name, p) in &queries {
let mut key = keys[name_id[name]];
if p == '?' {
println!("{}", map.binary_search(&key).unwrap() + 1);
} else {
let p = (p as u8 - b'A') as usize;
let (Reverse(score), _time) = map.remove(&key).unwrap();
key = (
Reverse(score + 50 * a[p] + 250 * a[p] / (5 + solved[p as usize])),
time,
);
solved[p as usize] += 1;
keys[name_id[name]] = key;
map.insert(key);
time += 1;
}
}
}
// input {{{
#[allow(dead_code)]
mod input {
use std::cell::Cell;
use std::convert::TryFrom;
use std::io::stdin;
use std::io::BufRead;
use std::io::BufReader;
use std::io::Lines;
use std::io::Stdin;
use std::str::FromStr;
use std::sync::Mutex;
use std::sync::Once;
type Server = Mutex<Lines<BufReader<Stdin>>>;
static ONCE: Once = Once::new();
pub struct Lazy(Cell<Option<Server>>);
unsafe impl Sync for Lazy {}
fn line() -> String {
static SYNCER: Lazy = Lazy(Cell::new(None));
ONCE.call_once(|| {
SYNCER
.0
.set(Some(Mutex::new(BufReader::new(stdin()).lines())));
});
unsafe {
(*SYNCER.0.as_ptr())
.as_ref()
.unwrap()
.lock()
.unwrap()
.next()
.unwrap()
.unwrap()
}
}
pub trait ForceFromStr: FromStr {
fn force_from_str(s: &str) -> Self;
}
impl<T, E> ForceFromStr for T
where
T: FromStr<Err = E>,
E: std::fmt::Debug,
{
fn force_from_str(s: &str) -> Self { s.parse().unwrap() }
}
pub fn input_array<T: ForceFromStr, const N: usize>() -> [T; N]
where
T: std::fmt::Debug,
{
<[_; N]>::try_from(input_vec()).unwrap()
}
pub fn input_vec<T: ForceFromStr>() -> Vec<T> {
line()
.split_whitespace()
.map(T::force_from_str)
.collect::<Vec<_>>()
}
pub fn input<T: ForceFromStr>() -> T { T::force_from_str(&line()) }
}
// }}}
// rb {{{
#[allow(dead_code)]
mod rb {
mod balance {
use core::fmt;
use std::ops::Deref;
use std::ops::DerefMut;
use std::ptr::NonNull;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Color {
Red,
Black,
}
pub trait Balance: Sized {
fn update(&mut self);
fn push(&mut self);
fn color(&mut self) -> &mut Color;
fn parent(&mut self) -> &mut Option<Ptr<Self>>;
fn left(&mut self) -> &mut Option<Ptr<Self>>;
fn right(&mut self) -> &mut Option<Ptr<Self>>;
}
pub struct Tree<T: Balance> {
pub root: Option<Ptr<T>>,
pub black_height: u8,
}
impl<T: Balance> Tree<T> {
pub fn new() -> Self {
Self {
root: None,
black_height: 0,
}
}
// Updates: the proper ancestors of `x` (i.e. `x` should be already updated)
pub fn fix_red(&mut self, mut x: Ptr<T>) {
while color(*x.parent()) == Color::Red {
let mut p = x.parent().unwrap();
let Some(mut pp) = p.parent() else {
p.update();
*p.color() = Color::Black;
self.black_height += 1;
return;
};
// Case 1: `p` is the left child.
if *pp.left() == Some(p) {
// Case 1.1: `pp` is a 5-node.
if color(*pp.right()) == Color::Red {
*p.color() = Color::Black;
*pp.color() = Color::Red;
*pp.right().unwrap().color() = Color::Black;
p.update();
pp.update();
x = pp;
}
// Case 1.2: `pp` is a splayed 4-node.
else if *p.right() == Some(x) {
rotate_left(p);
rotate_right(pp);
*x.color() = Color::Black;
*pp.color() = Color::Red;
p.update();
pp.update();
x.update();
break;
}
// Case 1.3: `pp` is a straight 4-node.
else {
rotate_right(pp);
*p.color() = Color::Black;
*pp.color() = Color::Red;
pp.update();
break;
}
}
// Case 2: `p` is the right child.
else {
// Case 2.1: `pp` is a 5-node.
if color(*pp.left()) == Color::Red {
*p.color() = Color::Black;
*pp.color() = Color::Red;
*pp.left().unwrap().color() = Color::Black;
p.update();
pp.update();
x = pp;
}
// Case 2.2: `pp` is a splayed 4-node.
else if *p.left() == Some(x) {
rotate_right(p);
rotate_left(pp);
*x.color() = Color::Black;
*pp.color() = Color::Red;
p.update();
pp.update();
x.update();
break;
}
// Case 2.3: `pp` is a straight 4-node.
else {
rotate_left(pp);
*p.color() = Color::Black;
*pp.color() = Color::Red;
pp.update();
break;
}
}
}
self.root = Some(x.update_ancestors());
}
// Updates: the proper ancestors of `x` (i.e. `x` should be already updated)
pub fn fix_black(&mut self, black_violation: BlackViolation<T>) {
let BlackViolation { p, mut x } = black_violation;
loop {
if color(x) == Color::Red {
*x.unwrap().color() = Color::Black;
break;
}
let p = x.map_or(p, |mut x| *x.parent());
let Some(mut p) = p else {
self.black_height -= 1;
return;
};
// Case 1: `x` is the left child.
if *p.left() == x {
let mut s = p.right().unwrap();
if *s.color() == Color::Red {
rotate_left(p);
*p.color() = Color::Red;
*s.color() = Color::Black;
s = p.right().unwrap();
}
match (color(*s.left()), color(*s.right())) {
// Case 1.1: `s` is a 2-node.
(Color::Black, Color::Black) => {
*s.color() = Color::Red;
p.update();
x = Some(p);
}
// Case 1.2: `s` is a left-leaning 3-node.
(Color::Red, Color::Black) => {
let mut c = s.left().unwrap();
rotate_right(s);
rotate_left(p);
*c.color() = *p.color();
*p.color() = Color::Black;
s.update();
break;
}
// Case 1.3: `s` is a right-leaning 3-node, or a 4-node.
(_, Color::Red) => {
rotate_left(p);
*s.color() = *p.color();
*p.color() = Color::Black;
*s.right().unwrap().color() = Color::Black;
break;
}
}
}
// Case 2: `x` is the right child.
else {
let mut s = p.left().unwrap();
if *s.color() == Color::Red {
rotate_right(p);
*p.color() = Color::Red;
*s.color() = Color::Black;
s = p.left().unwrap();
}
match (color(*s.left()), color(*s.right())) {
// Case 2.1: `s` is a 2-node.
(Color::Black, Color::Black) => {
*s.color() = Color::Red;
p.update();
x = Some(p);
}
// Case 2.2: `s` os a right-leaning 3-node.
(Color::Black, Color::Red) => {
let mut c = s.right().unwrap();
rotate_left(s);
rotate_right(p);
*c.color() = *p.color();
*p.color() = Color::Black;
s.update();
break;
}
// Case 2.3: `s` is a left-leaning 3-node, or a 4-node.
(Color::Red, _) => {
rotate_right(p);
*s.color() = *p.color();
*p.color() = Color::Black;
*s.left().unwrap().color() = Color::Black;
break;
}
}
}
}
self.root = Some(match x {
None => {
p.unwrap().update();
p.unwrap().update_ancestors()
}
Some(x) => x.update_ancestors(),
})
}
pub fn transplant(&mut self, mut place: Ptr<T>, new: Option<Ptr<T>>) {
if let Some(mut p) = *place.parent() {
*(if *p.left() == Some(place) { p.left() } else { p.right() }) = new;
} else {
self.root = new;
}
if let Some(mut new) = new {
*new.parent() = *place.parent();
}
}
}
pub struct BlackViolation<T: Balance> {
pub p: Option<Ptr<T>>,
pub x: Option<Ptr<T>>,
}
impl<T: Balance> PartialEq for BlackViolation<T> {
fn eq(&self, other: &Self) -> bool { (self.p, self.x) == (other.p, other.x) }
}
impl<T: Balance> fmt::Debug for BlackViolation<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("BlackViolation")
.field("p", &self.p)
.field("x", &self.x)
.finish()
}
}
impl<T: Balance> Clone for BlackViolation<T> {
fn clone(&self) -> Self {
Self {
p: self.p,
x: self.x,
}
}
}
impl<T: Balance> Copy for BlackViolation<T> {}
fn color<T: Balance>(x: Option<Ptr<T>>) -> Color {
match x {
None => Color::Black,
Some(mut x) => *x.color(),
}
}
fn rotate_left<T: Balance>(mut l: Ptr<T>) {
let p = *l.parent();
let mut r = l.right().unwrap();
let c = *r.left();
// Connect `p` and `r`.
*r.parent() = p;
if let Some(mut p) = p {
*(if *p.left() == Some(l) { p.left() } else { p.right() }) = Some(r);
}
// Connect `r` and `l`.
*l.parent() = Some(r);
*r.left() = Some(l);
// Connect `l` and `c`.
if let Some(mut c) = c {
*c.parent() = Some(l);
}
*l.right() = c;
}
fn rotate_right<T: Balance>(mut r: Ptr<T>) {
let p = *r.parent();
let mut l = r.left().unwrap();
let c = *l.right();
// Connect `p` and `l`.
*l.parent() = p;
if let Some(mut p) = p {
*(if *p.left() == Some(r) { p.left() } else { p.right() }) = Some(l);
}
// Connect `l` and `r`.
*r.parent() = Some(l);
*l.right() = Some(r);
// Connect `r` and `c`.
if let Some(mut c) = c {
*c.parent() = Some(r);
}
*r.left() = c;
}
pub struct Ptr<T>(NonNull<T>);
impl<T: Balance> Ptr<T> {
pub fn new(x: T) -> Self { Self(NonNull::from(Box::leak(Box::new(x)))) }
pub fn free(self) -> T { unsafe { *Box::from_raw(self.0.as_ptr()) } }
// Returns the root
pub fn update_ancestors(self) -> Self {
let mut x = self;
while let Some(mut p) = *x.parent() {
p.update();
x = p;
}
x
}
pub fn as_longlife_ref<'a>(self) -> &'a T { unsafe { self.0.as_ref() } }
pub fn as_longlife_mut<'a>(mut self) -> &'a mut T { unsafe { self.0.as_mut() } }
}
impl<T> Clone for Ptr<T> {
fn clone(&self) -> Self { *self }
}
impl<T> Copy for Ptr<T> {}
impl<T> Deref for Ptr<T> {
type Target = T;
fn deref(&self) -> &Self::Target { unsafe { self.0.as_ref() } }
}
impl<T> DerefMut for Ptr<T> {
fn deref_mut(&mut self) -> &mut Self::Target { unsafe { self.0.as_mut() } }
}
impl<T> fmt::Debug for Ptr<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{:02x}", self.0.as_ptr() as usize % 0x1000 / 0x10)
}
}
impl<T> PartialEq for Ptr<T> {
fn eq(&self, other: &Self) -> bool { std::ptr::eq(self.0.as_ptr(), other.0.as_ptr()) }
}
}
mod map {
use crate::rb::balance::Balance;
use crate::rb::balance::BlackViolation;
use crate::rb::balance::Color;
use crate::rb::balance::Ptr;
use crate::rb::balance::Tree;
use std::borrow::Borrow;
use std::cmp::Ordering;
use std::marker::PhantomData;
pub trait SegmapOp {
type Value;
type Acc;
type Lazy: PartialEq;
fn to_acc(value: &Self::Value) -> Self::Acc;
fn join(
lhs: Option<&Self::Acc>,
center: &Self::Value,
rhs: Option<&Self::Acc>,
) -> Self::Acc;
fn apply(_value: &mut Self::Value, _lazy: &Self::Lazy);
fn compose(_lhs: &Self::Lazy, _rhs: &Self::Lazy) -> Self::Lazy;
fn identity() -> Self::Lazy;
fn is_identity(lazy: &Self::Lazy) -> bool { *lazy == Self::identity() }
}
#[allow(dead_code)]
pub struct Node<K, O: SegmapOp> {
key: K,
value: O::Value,
acc: O::Acc,
lazy: O::Lazy,
parent: Option<Ptr<Node<K, O>>>,
left: Option<Ptr<Node<K, O>>>,
right: Option<Ptr<Node<K, O>>>,
len: usize,
color: Color,
}
impl<K: Ord, O: SegmapOp> Node<K, O> {
pub fn new(key: K, value: O::Value, color: Color) -> Self {
Self {
key,
acc: O::to_acc(&value),
value,
lazy: O::identity(),
parent: None,
left: None,
right: None,
len: 1,
color,
}
}
}
fn len<K, O: SegmapOp>(node: Option<Ptr<Node<K, O>>>) -> usize {
node.as_ref().map_or(0, |node| node.len)
}
fn acc<K, O: SegmapOp>(node: &Option<Ptr<Node<K, O>>>) -> Option<&O::Acc> {
node.as_ref().map(|node| &node.acc)
}
impl<K, O: SegmapOp> Balance for Node<K, O> {
fn update(&mut self) {
self.len = len(self.left) + 1 + len(self.right);
self.acc = O::join(acc(&self.left), &self.value, acc(&self.right));
}
fn push(&mut self) {}
fn color(&mut self) -> &mut Color { &mut self.color }
fn parent(&mut self) -> &mut Option<Ptr<Self>> { &mut self.parent }
fn left(&mut self) -> &mut Option<Ptr<Self>> { &mut self.left }
fn right(&mut self) -> &mut Option<Ptr<Self>> { &mut self.right }
}
pub struct Segmap<K, O: SegmapOp> {
tree: Tree<Node<K, O>>,
}
impl<K: Ord, O: SegmapOp> Segmap<K, O> {
pub fn new() -> Self { Self { tree: Tree::new() } }
pub fn len(&self) -> usize { len(self.tree.root) }
pub fn is_empty(&self) -> bool { self.tree.root.is_none() }
pub fn nth(&self, n: usize) -> (&K, &O::Value) {
let x = self.nth_ptr(n).as_longlife_ref();
(&x.key, &x.value)
}
pub fn nth_mut(&mut self, n: usize) -> (&K, &mut O::Value) {
let x = self.nth_ptr(n).as_longlife_mut();
(&x.key, &mut x.value)
}
pub fn binary_search<Q: ?Sized>(&self, key: &Q) -> Option<&O::Value>
where
K: Ord + Borrow<Q>,
Q: Ord,
{
self.binary_search_ptr(key)
.map(|(x, _)| &x.as_longlife_ref().value)
}
pub fn binary_search_index<Q: ?Sized>(&self, key: &Q) -> Option<usize>
where
K: Ord + Borrow<Q>,
Q: Ord,
{
self.binary_search_ptr(key).map(|(_, i)| i)
}
pub fn insert(&mut self, key: K, value: O::Value) {
let mut new = Ptr::new(Node::new(key, value, Color::Red));
let Some(mut x) = self.tree.root else {
new.color = Color::Black;
self.tree.root = Some(new);
self.tree.black_height = 1;
return;
};
let key = &new.key;
loop {
match key.cmp(&x.key) {
Ordering::Less | Ordering::Equal => {
if let Some(left) = x.left {
x = left;
} else {
new.parent = Some(x);
x.left = Some(new);
break;
}
}
Ordering::Greater => {
if let Some(right) = x.right {
x = right;
} else {
new.parent = Some(x);
x.right = Some(new);
break;
}
}
}
}
if x.color == Color::Red {
self.tree.fix_red(new);
} else {
new.update_ancestors();
}
}
pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, O::Value)>
where
K: Ord + Borrow<Q>,
Q: Ord,
{
let x = self.binary_search_ptr(key)?.0;
self.remove_ptr(x);
let x = x.free();
Some((x.key, x.value))
}
pub fn remove_nth(&mut self, n: usize) -> (K, O::Value) {
let x = self.nth_ptr(n);
self.remove_ptr(x);
let x = x.free();
(x.key, x.value)
}
fn nth_ptr(&self, mut n: usize) -> Ptr<Node<K, O>> {
assert!(
n < self.len(),
"Index out of range: n = {n}, while len = {}",
self.len()
);
let mut x = self.tree.root.unwrap();
loop {
let left_len = len(x.left);
x = match n.cmp(&left_len) {
Ordering::Less => x.left.unwrap(),
Ordering::Equal => break,
Ordering::Greater => {
n -= left_len + 1;
x.right.unwrap()
}
};
}
x
}
pub fn binary_search_ptr<Q: ?Sized>(&self, key: &Q) -> Option<(Ptr<Node<K, O>>, usize)>
where
K: Ord + Borrow<Q>,
Q: Ord,
{
let mut x = self.tree.root?;
let mut index = 0;
loop {
x = match key.cmp(x.key.borrow()) {
Ordering::Less => x.left?,
Ordering::Greater => {
index += len(x.left) + 1;
x.right?
}
Ordering::Equal => break,
}
}
Some((x, index + len(x.left)))
}
fn remove_ptr(&mut self, x: Ptr<Node<K, O>>) {
let needs_fix;
let black_vio;
match (x.left, x.right) {
(Some(_), Some(top)) => {
let mut next = top;
while let Some(left) = next.left {
next = left;
}
needs_fix = next.color == Color::Black;
next.left = x.left;
x.left.unwrap().parent = Some(next);
next.color = x.color;
if top == next {
black_vio = BlackViolation {
p: Some(next),
x: next.right,
};
self.tree.transplant(x, Some(next));
} else {
black_vio = BlackViolation {
p: next.parent,
x: next.right,
};
self.tree.transplant(next, next.right);
next.right = x.right;
if let Some(mut r) = next.right {
r.parent = Some(next);
}
self.tree.transplant(x, Some(next));
}
}
(None, Some(_)) => {
needs_fix = x.color == Color::Black;
black_vio = BlackViolation {
p: x.parent,
x: x.right,
};
self.tree.transplant(x, x.right);
}
(_, None) => {
needs_fix = x.color == Color::Black;
black_vio = BlackViolation {
p: x.parent,
x: x.left,
};
self.tree.transplant(x, x.left);
}
}
if needs_fix {
self.tree.fix_black(black_vio);
} else if let Some(mut p) = black_vio.p {
p.update();
p.update_ancestors();
}
}
}
impl<K: Ord, O: SegmapOp> Default for Segmap<K, O> {
fn default() -> Self { Self::new() }
}
struct Nop<T>(PhantomData<T>);
impl<T> SegmapOp for Nop<T> {
type Acc = ();
type Lazy = ();
type Value = T;
fn to_acc(_value: &Self::Value) -> Self::Acc {}
fn join(
_lhs: Option<&Self::Acc>,
_center: &Self::Value,
_rhs: Option<&Self::Acc>,
) -> Self::Acc {
}
fn apply(_value: &mut Self::Value, _lazy: &Self::Lazy) {}
fn compose(_lhs: &Self::Lazy, _rhs: &Self::Lazy) -> Self::Lazy {}
fn identity() -> Self::Lazy {}
}
pub struct Multimap<K, V> {
segmap: Segmap<K, Nop<V>>,
}
impl<K: Ord, V> Multimap<K, V> {
pub fn new() -> Self {
Self {
segmap: Segmap::new(),
}
}
pub fn len(&self) -> usize { self.segmap.len() }
pub fn is_empty(&self) -> bool { self.segmap.is_empty() }
pub fn nth(&self, n: usize) -> (&K, &V) { self.segmap.nth(n) }
pub fn binary_search<Q: ?Sized>(&self, key: &Q) -> Option<&V>
where
K: Ord + Borrow<Q>,
Q: Ord,
{
self.segmap.binary_search(key)
}
pub fn binary_search_index<Q: ?Sized>(&self, key: &Q) -> Option<usize>
where
K: Ord + Borrow<Q>,
Q: Ord,
{
self.segmap.binary_search_index(key)
}
pub fn insert(&mut self, key: K, value: V) { self.segmap.insert(key, value) }
pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
where
K: Ord + Borrow<Q>,
Q: Ord,
{
self.segmap.remove(key)
}
pub fn remove_nth(&mut self, n: usize) -> (K, V) { self.segmap.remove_nth(n) }
}
impl<K: Ord, V> Default for Multimap<K, V> {
fn default() -> Self { Self::new() }
}
pub struct Multiset<K> {
map: Multimap<K, ()>,
}
impl<K: Ord> Multiset<K> {
pub fn new() -> Self {
Self {
map: Multimap::new(),
}
}
pub fn len(&self) -> usize { self.map.len() }
pub fn is_empty(&self) -> bool { self.map.is_empty() }
pub fn nth(&self, n: usize) -> &K { self.map.nth(n).0 }
pub fn binary_search<Q: ?Sized>(&self, key: &Q) -> Option<usize>
where
K: Ord + Borrow<Q>,
Q: Ord,
{
self.map.binary_search_index(key)
}
pub fn insert(&mut self, key: K) { self.map.insert(key, ()) }
pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<K>
where
K: Ord + Borrow<Q>,
Q: Ord,
{
self.map.remove(key).map(|(k, _)| k)
}
pub fn remove_nth(&mut self, n: usize) -> K { self.map.remove_nth(n).0 }
}
impl<K: Ord> Default for Multiset<K> {
fn default() -> Self { Self::new() }
}
}
pub use map::Multimap;
pub use map::Multiset;
pub use map::Segmap;
pub use map::SegmapOp;
}
// }}}