use input::input; use input::input_array; use input::input_vec; use std::cmp::Reverse; use std::collections::HashMap; fn main() { let _ = input::(); let a = input_vec::(); let q = input::(); let queries = std::iter::repeat_with(|| { let [name, p] = input_array::(); (name, p.parse::().unwrap()) }) .take(q) .collect::>(); 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>>; static ONCE: Once = Once::new(); pub struct Lazy(Cell>); 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 ForceFromStr for T where T: FromStr, E: std::fmt::Debug, { fn force_from_str(s: &str) -> Self { s.parse().unwrap() } } pub fn input_array() -> [T; N] where T: std::fmt::Debug, { <[_; N]>::try_from(input_vec()).unwrap() } pub fn input_vec() -> Vec { line() .split_whitespace() .map(T::force_from_str) .collect::>() } pub fn input() -> 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>; fn left(&mut self) -> &mut Option>; fn right(&mut self) -> &mut Option>; } pub struct Tree { pub root: Option>, pub black_height: u8, } impl Tree { 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) { 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) { 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, new: Option>) { 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 { pub p: Option>, pub x: Option>, } impl PartialEq for BlackViolation { fn eq(&self, other: &Self) -> bool { (self.p, self.x) == (other.p, other.x) } } impl fmt::Debug for BlackViolation { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_struct("BlackViolation") .field("p", &self.p) .field("x", &self.x) .finish() } } impl Clone for BlackViolation { fn clone(&self) -> Self { Self { p: self.p, x: self.x, } } } impl Copy for BlackViolation {} fn color(x: Option>) -> Color { match x { None => Color::Black, Some(mut x) => *x.color(), } } fn rotate_left(mut l: Ptr) { 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(mut r: Ptr) { 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(NonNull); impl Ptr { 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 Clone for Ptr { fn clone(&self) -> Self { *self } } impl Copy for Ptr {} impl Deref for Ptr { type Target = T; fn deref(&self) -> &Self::Target { unsafe { self.0.as_ref() } } } impl DerefMut for Ptr { fn deref_mut(&mut self) -> &mut Self::Target { unsafe { self.0.as_mut() } } } impl fmt::Debug for Ptr { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "{:02x}", self.0.as_ptr() as usize % 0x1000 / 0x10) } } impl PartialEq for Ptr { 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 { key: K, value: O::Value, acc: O::Acc, lazy: O::Lazy, parent: Option>>, left: Option>>, right: Option>>, len: usize, color: Color, } impl Node { 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(node: Option>>) -> usize { node.as_ref().map_or(0, |node| node.len) } fn acc(node: &Option>>) -> Option<&O::Acc> { node.as_ref().map(|node| &node.acc) } impl Balance for Node { 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> { &mut self.parent } fn left(&mut self) -> &mut Option> { &mut self.left } fn right(&mut self) -> &mut Option> { &mut self.right } } pub struct Segmap { tree: Tree>, } impl Segmap { 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(&self, key: &Q) -> Option<&O::Value> where K: Ord + Borrow, Q: Ord, { self.binary_search_ptr(key) .map(|(x, _)| &x.as_longlife_ref().value) } pub fn binary_search_index(&self, key: &Q) -> Option where K: Ord + Borrow, 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(&mut self, key: &Q) -> Option<(K, O::Value)> where K: Ord + Borrow, 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> { 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(&self, key: &Q) -> Option<(Ptr>, usize)> where K: Ord + Borrow, 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>) { 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 Default for Segmap { fn default() -> Self { Self::new() } } struct Nop(PhantomData); impl SegmapOp for Nop { 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 { segmap: Segmap>, } impl Multimap { 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(&self, key: &Q) -> Option<&V> where K: Ord + Borrow, Q: Ord, { self.segmap.binary_search(key) } pub fn binary_search_index(&self, key: &Q) -> Option where K: Ord + Borrow, 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(&mut self, key: &Q) -> Option<(K, V)> where K: Ord + Borrow, Q: Ord, { self.segmap.remove(key) } pub fn remove_nth(&mut self, n: usize) -> (K, V) { self.segmap.remove_nth(n) } } impl Default for Multimap { fn default() -> Self { Self::new() } } pub struct Multiset { map: Multimap, } impl Multiset { 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(&self, key: &Q) -> Option where K: Ord + Borrow, Q: Ord, { self.map.binary_search_index(key) } pub fn insert(&mut self, key: K) { self.map.insert(key, ()) } pub fn remove(&mut self, key: &Q) -> Option where K: Ord + Borrow, 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 Default for Multiset { fn default() -> Self { Self::new() } } } pub use map::Multimap; pub use map::Multiset; pub use map::Segmap; pub use map::SegmapOp; } // }}}