QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#196634 | #7513. Palindromic Beads | ucup-team296 | AC ✓ | 1123ms | 161588kb | Rust | 44.3kb | 2023-10-01 20:45:47 | 2023-10-01 20:45:48 |
Judging History
answer
pub mod solution {
//{"name":"b","group":"Manual","url":"","interactive":false,"timeLimit":2000,"tests":[{"input":"","output":""},{"input":"","output":""}],"testType":"single","input":{"type":"stdin","fileName":null,"pattern":null},"output":{"type":"stdout","fileName":null,"pattern":null},"languages":{"java":{"taskClass":"b"}}}
use std::cmp::Reverse;
use std::ops::Range;
use crate::algo_lib::io::output::output;
use crate::algo_lib::io::task_io_settings::TaskIoType;
use crate::algo_lib::io::task_runner::run_task;
use crate::algo_lib::io::input::Input;
use crate::algo_lib::io::task_io_settings::TaskIoSettings;
use crate::algo_lib::misc::min_max::UpdateMinMax;
use crate::algo_lib::misc::rec_function::Callable3;
use crate::algo_lib::misc::rec_function::RecursiveFunction3;
use crate::algo_lib::misc::vec_apply_delta::ApplyDelta;
use crate::algo_lib::seg_trees::hld::Hld;
use crate::algo_lib::seg_trees::seg_tree_2d::SegTree2d;
use crate::algo_lib::seg_trees::seg_tree_trait::SegTreeNode;
#[allow(unused)]
use crate::dbg;
use crate::out;
use crate::out_line;
#[derive(Clone, Copy, Default, Debug)]
pub struct VertexInfo {
pub pos: usize,
// range is [pos..max_subtree_pos)
pub max_subtree_pos: usize,
pub parent: usize,
pub height: usize,
}
impl VertexInfo {
pub fn range(&self) -> Range<usize> {
self.pos..self.max_subtree_pos
}
}
#[derive(Debug)]
pub struct DfsOrder {
pub order: Vec<usize>,
pub info: Vec<VertexInfo>,
}
impl DfsOrder {
pub fn new(g: &[Vec<usize>], root: usize) -> Self {
let n = g.len();
let mut order = vec![];
let mut info = vec![VertexInfo::default(); n];
RecursiveFunction3::new(|f, v: usize, p: usize, h: usize| {
order.push(v);
info[v].pos = order.len() - 1;
info[v].max_subtree_pos = order.len();
info[v].parent = p;
info[v].height = h;
for &to in g[v].iter() {
if to != p {
f.call(to, v, h + 1);
let max_subtree_pos = info[to].max_subtree_pos;
info[v].max_subtree_pos.update_max(max_subtree_pos);
}
}
})
.call(root, root, 0);
assert_eq!(order.len(), n);
Self { order, info }
}
pub fn is_in_subtree_of(&self, v: usize, anc: usize) -> bool {
self.info[anc].pos <= self.info[v].pos && self.info[v].pos < self.info[anc].max_subtree_pos
}
}
#[derive(Clone, Copy, Debug)]
struct Color {
min_v: usize,
max_v: usize,
dist: usize,
}
struct Point {
x: usize,
y: usize,
value: usize,
}
struct SlowSegTree2D {
nodes: Vec<Point>,
}
impl SlowSegTree2D {
pub fn new() -> Self {
Self { nodes: vec![] }
}
pub fn get_max(&self, x_range: Range<usize>, y_range: Range<usize>) -> usize {
let mut res = 0;
for p in self.nodes.iter() {
if x_range.contains(&p.x) && y_range.contains(&p.y) {
res.update_max(p.value);
}
}
res
}
pub fn add(&mut self, x: usize, y: usize, value: usize) {
self.nodes.push(Point { x, y, value });
}
}
#[derive(Clone, Copy, Default)]
struct Node {
value: i32,
}
impl SegTreeNode for Node {
fn join_nodes(l: &Self, r: &Self, context: &Self::Context) -> Self {
Self {
value: l.value.max(r.value),
}
}
fn apply_update(node: &mut Self, update: &Self::Update) {
todo!()
}
fn join_updates(current: &mut Self::Update, add: &Self::Update) {
todo!()
}
type Update = ();
type Context = ();
}
fn solve(input: &mut Input, _test_case: usize) {
let n = input.usize();
let colors = input.vec::<usize>(n).sub_from_all(1);
let mut g = vec![vec![]; n];
for _ in 0..n - 1 {
let u = input.usize() - 1;
let v = input.usize() - 1;
g[u].push(v);
g[v].push(u);
}
let hld = Hld::new(g.clone(), 0);
let dfs_order = DfsOrder::new(&g, 0);
let mut by_color = vec![vec![]; n];
for v in 0..n {
by_color[colors[v]].push(v);
}
let mut pairs = vec![];
for color in 0..colors.len() {
if by_color[color].len() == 2 {
let (v, u) = (by_color[color][0], by_color[color][1]);
let lca = hld.lca(v, u);
let dist = dfs_order.info[v].height + dfs_order.info[u].height
- 2 * dfs_order.info[lca].height;
let pos1 = dfs_order.info[v].pos;
let pos2 = dfs_order.info[u].pos;
let (min_v, max_v) = if pos1 < pos2 { (v, u) } else { (u, v) };
pairs.push(Color { min_v, max_v, dist })
}
}
let mut st_pts: Vec<_> = pairs
.iter()
.map(|p| (dfs_order.info[p.min_v].pos, dfs_order.info[p.max_v].pos))
.collect();
st_pts.push((0, 0));
let mut st = SegTree2d::<usize, Node>::new(st_pts);
pairs.sort_by_key(|p| Reverse(p.dist));
let mut glob_res = 1;
for pair in pairs.iter() {
let (min_v, max_v) = (pair.min_v, pair.max_v);
let mut res;
if dfs_order.is_in_subtree_of(max_v, min_v) {
res = st
.query(0..dfs_order.info[min_v].pos, dfs_order.info[max_v].range())
.value;
res.update_max(
st.query(
dfs_order.info[max_v].range(),
dfs_order.info[min_v].max_subtree_pos..n,
)
.value,
);
for &to in g[min_v].iter() {
if !dfs_order.is_in_subtree_of(max_v, to) && dfs_order.info[min_v].parent != to {
let r1 = dfs_order.info[max_v].range();
let r2 = dfs_order.info[to].range();
if r1.start < r2.start {
res.update_max(st.query(r1, r2).value);
} else {
res.update_max(st.query(r2, r1).value);
}
}
}
} else {
res = st
.query(dfs_order.info[min_v].range(), dfs_order.info[max_v].range())
.value;
}
let mut update_res = res + 2;
st.update(
dfs_order.info[min_v].pos,
dfs_order.info[max_v].pos,
Node { value: update_res },
);
if dfs_order.info[max_v].parent != min_v {
update_res += 1;
}
glob_res.update_max(update_res);
}
out_line!(glob_res);
}
pub(crate) fn run(mut input: Input) -> bool {
solve(&mut input, 1);
output().flush();
true
}
#[allow(unused)]
pub fn submit() -> bool {
let io = TaskIoSettings {
is_interactive: false,
input: TaskIoType::Std,
output: TaskIoType::Std,
};
run_task(io, run)
}
}
pub mod algo_lib {
pub mod io {
pub mod input {
use std::fmt::Debug;
use std::io::Read;
use std::marker::PhantomData;
use std::path::Path;
use std::str::FromStr;
pub struct Input {
input: Box<dyn Read>,
buf: Vec<u8>,
at: usize,
buf_read: usize,
}
macro_rules! read_integer_fun {
($t:ident) => {
#[allow(unused)]
pub fn $t(&mut self) -> $t {
self.read_integer()
}
};
}
impl Input {
const DEFAULT_BUF_SIZE: usize = 4096;
///
/// Using with stdin:
/// ```no_run
/// use algo_lib::io::input::Input;
/// let stdin = std::io::stdin();
/// let input = Input::new(Box::new(stdin));
/// ```
///
/// For read files use ``new_file`` instead.
///
///
pub fn new(input: Box<dyn Read>) -> Self {
Self {
input,
buf: vec![0; Self::DEFAULT_BUF_SIZE],
at: 0,
buf_read: 0,
}
}
pub fn new_file<P: AsRef<Path>>(path: P) -> Self {
let file = std::fs::File::open(&path)
.unwrap_or_else(|_| panic!("Can't open file: {:?}", path.as_ref().as_os_str()));
Self::new(Box::new(file))
}
pub fn new_with_size(input: Box<dyn Read>, buf_size: usize) -> Self {
Self {
input,
buf: vec![0; buf_size],
at: 0,
buf_read: 0,
}
}
pub fn new_file_with_size<P: AsRef<Path>>(path: P, buf_size: usize) -> Self {
let file = std::fs::File::open(&path)
.unwrap_or_else(|_| panic!("Can't open file: {:?}", path.as_ref().as_os_str()));
Self::new_with_size(Box::new(file), buf_size)
}
pub fn get(&mut self) -> Option<u8> {
if self.refill_buffer() {
let res = self.buf[self.at];
self.at += 1;
Some(res)
} else {
None
}
}
pub fn peek(&mut self) -> Option<u8> {
if self.refill_buffer() {
Some(self.buf[self.at])
} else {
None
}
}
pub fn skip_whitespace(&mut self) {
while let Some(b) = self.peek() {
if !char::from(b).is_whitespace() {
return;
}
self.get();
}
}
pub fn next_token(&mut self) -> Option<Vec<u8>> {
self.skip_whitespace();
let mut res = Vec::new();
while let Some(c) = self.get() {
if char::from(c).is_whitespace() {
break;
}
res.push(c);
}
if res.is_empty() {
None
} else {
Some(res)
}
}
//noinspection RsSelfConvention
pub fn is_exhausted(&mut self) -> bool {
self.peek().is_none()
}
pub fn has_more_elements(&mut self) -> bool {
!self.is_exhausted()
}
pub fn read<T: Readable>(&mut self) -> T {
T::read(self)
}
pub fn vec<T: Readable>(&mut self, size: usize) -> Vec<T> {
let mut res = Vec::with_capacity(size);
for _ in 0usize..size {
res.push(self.read());
}
res
}
pub fn string_vec(&mut self, size: usize) -> Vec<Vec<u8>> {
let mut res = Vec::with_capacity(size);
for _ in 0usize..size {
res.push(self.string());
}
res
}
pub fn read_line(&mut self) -> String {
let mut res = String::new();
while let Some(c) = self.get() {
if c == b'\n' {
break;
}
if c == b'\r' {
if self.peek() == Some(b'\n') {
self.get();
}
break;
}
res.push(c.into());
}
res
}
#[allow(clippy::should_implement_trait)]
pub fn into_iter<T: Readable>(self) -> InputIterator<T> {
InputIterator {
input: self,
phantom: Default::default(),
}
}
fn read_integer<T: FromStr>(&mut self) -> T
where
<T as FromStr>::Err: Debug,
{
let res = self.read_string();
res.parse::<T>().unwrap()
}
fn read_string(&mut self) -> String {
match self.next_token() {
None => {
panic!("Input exhausted");
}
Some(res) => unsafe { String::from_utf8_unchecked(res) },
}
}
pub fn string_as_string(&mut self) -> String {
self.read_string()
}
pub fn string(&mut self) -> Vec<u8> {
self.read_string().into_bytes()
}
fn read_char(&mut self) -> char {
self.skip_whitespace();
self.get().unwrap().into()
}
fn read_float(&mut self) -> f64 {
self.read_string().parse().unwrap()
}
pub fn f64(&mut self) -> f64 {
self.read_float()
}
fn refill_buffer(&mut self) -> bool {
if self.at == self.buf_read {
self.at = 0;
self.buf_read = self.input.read(&mut self.buf).unwrap();
self.buf_read != 0
} else {
true
}
}
read_integer_fun!(i32);
read_integer_fun!(i64);
read_integer_fun!(i128);
read_integer_fun!(u32);
read_integer_fun!(u64);
read_integer_fun!(usize);
}
pub trait Readable {
fn read(input: &mut Input) -> Self;
}
impl Readable for String {
fn read(input: &mut Input) -> Self {
input.read_string()
}
}
impl Readable for char {
fn read(input: &mut Input) -> Self {
input.read_char()
}
}
impl Readable for f64 {
fn read(input: &mut Input) -> Self {
input.read_string().parse().unwrap()
}
}
impl Readable for f32 {
fn read(input: &mut Input) -> Self {
input.read_string().parse().unwrap()
}
}
impl<T: Readable> Readable for Vec<T> {
fn read(input: &mut Input) -> Self {
let size = input.read();
input.vec(size)
}
}
pub struct InputIterator<T: Readable> {
input: Input,
phantom: PhantomData<T>,
}
impl<T: Readable> Iterator for InputIterator<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.input.skip_whitespace();
self.input.peek().map(|_| self.input.read())
}
}
macro_rules! read_integer {
($t:ident) => {
impl Readable for $t {
fn read(input: &mut Input) -> Self {
input.read_integer()
}
}
};
}
read_integer!(i8);
read_integer!(i16);
read_integer!(i32);
read_integer!(i64);
read_integer!(i128);
read_integer!(isize);
read_integer!(u8);
read_integer!(u16);
read_integer!(u32);
read_integer!(u64);
read_integer!(u128);
read_integer!(usize);
}
pub mod output {
use std::io::Write;
pub struct Output {
output: Box<dyn Write>,
buf: Vec<u8>,
at: usize,
auto_flush: bool,
}
impl Output {
const DEFAULT_BUF_SIZE: usize = 4096;
pub fn new(output: Box<dyn Write>) -> Self {
Self {
output,
buf: vec![0; Self::DEFAULT_BUF_SIZE],
at: 0,
auto_flush: false,
}
}
pub fn new_with_auto_flush(output: Box<dyn Write>) -> Self {
Self {
output,
buf: vec![0; Self::DEFAULT_BUF_SIZE],
at: 0,
auto_flush: true,
}
}
pub fn flush(&mut self) {
if self.at != 0 {
self.output.write_all(&self.buf[..self.at]).unwrap();
self.at = 0;
self.output.flush().expect("Couldn't flush output");
}
}
pub fn print<T: Writable>(&mut self, s: &T) {
s.write(self);
}
pub fn put(&mut self, b: u8) {
self.buf[self.at] = b;
self.at += 1;
if self.at == self.buf.len() {
self.flush();
}
}
pub fn maybe_flush(&mut self) {
if self.auto_flush {
self.flush();
}
}
pub fn print_per_line<T: Writable>(&mut self, arg: &[T]) {
for i in arg {
i.write(self);
self.put(b'\n');
}
}
pub fn print_iter<T: Writable, I: Iterator<Item = T>>(&mut self, iter: I) {
let mut first = true;
for e in iter {
if first {
first = false;
} else {
self.put(b' ');
}
e.write(self);
}
}
pub fn print_iter_ref<'a, T: 'a + Writable, I: Iterator<Item = &'a T>>(&mut self, iter: I) {
let mut first = true;
for e in iter {
if first {
first = false;
} else {
self.put(b' ');
}
e.write(self);
}
}
}
impl Write for Output {
fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
let mut start = 0usize;
let mut rem = buf.len();
while rem > 0 {
let len = (self.buf.len() - self.at).min(rem);
self.buf[self.at..self.at + len].copy_from_slice(&buf[start..start + len]);
self.at += len;
if self.at == self.buf.len() {
self.flush();
}
start += len;
rem -= len;
}
if self.auto_flush {
self.flush();
}
Ok(buf.len())
}
fn flush(&mut self) -> std::io::Result<()> {
self.flush();
Ok(())
}
}
pub trait Writable {
fn write(&self, output: &mut Output);
}
impl Writable for &str {
fn write(&self, output: &mut Output) {
output.write_all(self.as_bytes()).unwrap();
}
}
impl Writable for String {
fn write(&self, output: &mut Output) {
output.write_all(self.as_bytes()).unwrap();
}
}
impl Writable for char {
fn write(&self, output: &mut Output) {
output.put(*self as u8);
}
}
impl<T: Writable> Writable for [T] {
fn write(&self, output: &mut Output) {
output.print_iter_ref(self.iter());
}
}
impl<T: Writable> Writable for Vec<T> {
fn write(&self, output: &mut Output) {
self[..].write(output);
}
}
macro_rules! write_to_string {
($t:ident) => {
impl Writable for $t {
fn write(&self, output: &mut Output) {
self.to_string().write(output);
}
}
};
}
write_to_string!(u8);
write_to_string!(u16);
write_to_string!(u32);
write_to_string!(u64);
write_to_string!(u128);
write_to_string!(usize);
write_to_string!(i8);
write_to_string!(i16);
write_to_string!(i32);
write_to_string!(i64);
write_to_string!(i128);
write_to_string!(isize);
write_to_string!(f32);
write_to_string!(f64);
impl<T: Writable, U: Writable> Writable for (T, U) {
fn write(&self, output: &mut Output) {
self.0.write(output);
output.put(b' ');
self.1.write(output);
}
}
impl<T: Writable, U: Writable, V: Writable> Writable for (T, U, V) {
fn write(&self, output: &mut Output) {
self.0.write(output);
output.put(b' ');
self.1.write(output);
output.put(b' ');
self.2.write(output);
}
}
pub static mut OUTPUT: Option<Output> = None;
pub fn set_global_output_to_stdout() {
unsafe {
OUTPUT = Some(Output::new(Box::new(std::io::stdout())));
}
}
pub fn set_global_output_to_file(path: &str) {
unsafe {
let out_file =
std::fs::File::create(path).unwrap_or_else(|_| panic!("Can't create file {}", path));
OUTPUT = Some(Output::new(Box::new(out_file)));
}
}
pub fn set_global_output_to_none() {
unsafe {
match &mut OUTPUT {
None => {}
Some(output) => output.flush(),
}
OUTPUT = None;
}
}
pub fn output() -> &'static mut Output {
unsafe {
match &mut OUTPUT {
None => {
panic!("Global output wasn't initialized");
}
Some(output) => output,
}
}
}
#[macro_export]
macro_rules! out {
($first: expr $(,$args:expr )*) => {
output().print(&$first);
$(output().put(b' ');
output().print(&$args);
)*
output().maybe_flush();
}
}
#[macro_export]
macro_rules! out_line {
($first: expr $(, $args:expr )* ) => {
{
out!($first $(,$args)*);
output().put(b'\n');
output().maybe_flush();
}
};
() => {
{
output().put(b'\n');
output().maybe_flush();
}
};
}
}
pub mod task_io_settings {
pub enum TaskIoType {
Std,
File(String),
}
pub struct TaskIoSettings {
pub is_interactive: bool,
pub input: TaskIoType,
pub output: TaskIoType,
}
}
pub mod task_runner {
use std::io::Write;
use super::input::Input;
use super::output::Output;
use super::output::OUTPUT;
use super::task_io_settings::TaskIoSettings;
use super::task_io_settings::TaskIoType;
pub fn run_task<Res>(io: TaskIoSettings, run: impl FnOnce(Input) -> Res) -> Res {
let output: Box<dyn Write> = match io.output {
TaskIoType::Std => Box::new(std::io::stdout()),
TaskIoType::File(file) => {
let out_file = std::fs::File::create(file).unwrap();
Box::new(out_file)
}
};
unsafe {
OUTPUT = Some(Output::new(output));
}
let input = match io.input {
TaskIoType::Std => {
let sin = std::io::stdin();
Input::new(Box::new(sin))
}
TaskIoType::File(file) => Input::new_file(file),
};
run(input)
}
}
}
pub mod misc {
pub mod binary_search {
use crate::algo_lib::misc::num_traits::Number;
use std::ops::Range;
pub fn binary_search_first_true<T>(range: Range<T>, mut f: impl FnMut(T) -> bool) -> T
where
T: Number,
{
// we can't store [range.start - 1] into [left], because it could overflow
let mut left_plus_one = range.start;
let mut right = range.end;
while right > left_plus_one {
let mid = left_plus_one + (right - left_plus_one) / T::TWO;
if f(mid) {
right = mid;
} else {
left_plus_one = mid + T::ONE;
}
}
right
}
pub fn binary_search_last_true<T>(range: Range<T>, mut f: impl FnMut(T) -> bool) -> Option<T>
where
T: Number,
{
let first_false = binary_search_first_true(range.clone(), |x| !f(x));
if first_false == range.start {
None
} else {
Some(first_false - T::ONE)
}
}
#[test]
fn simple_stress() {
const N: usize = 50;
for n in 1..N {
for cnt_false in 0..=n {
let mut a = vec![false; cnt_false];
a.resize(n, true);
let mut max_f_calls = ((n + 1) as f64).log2().ceil() as i32;
let f_is_true = |id: usize| -> bool {
max_f_calls -= 1;
assert!(max_f_calls >= 0);
a[id]
};
let result = binary_search_first_true(0..n, f_is_true);
assert_eq!(result, cnt_false);
}
}
}
}
pub mod dbg_macro {
#[macro_export]
#[allow(unused_macros)]
macro_rules! dbg {
($first_val:expr, $($val:expr),+ $(,)?) => {
eprint!("[{}:{}] {} = {:?}",
file!(), line!(), stringify!($first_val), &$first_val);
($(eprint!(", {} = {:?}", stringify!($val), &$val)),+,);
eprintln!();
};
($first_val:expr) => {
eprintln!("[{}:{}] {} = {:?}",
file!(), line!(), stringify!($first_val), &$first_val)
};
}
}
pub mod min_max {
pub trait UpdateMinMax: PartialOrd + Sized {
#[inline(always)]
fn update_min(&mut self, other: Self) -> bool {
if other < *self {
*self = other;
true
} else {
false
}
}
#[inline(always)]
fn update_max(&mut self, other: Self) -> bool {
if other > *self {
*self = other;
true
} else {
false
}
}
}
impl<T: PartialOrd + Sized> UpdateMinMax for T {}
pub trait FindMinMaxPos {
fn index_of_min(&self) -> usize;
fn index_of_max(&self) -> usize;
}
impl<T: PartialOrd> FindMinMaxPos for [T] {
fn index_of_min(&self) -> usize {
let mut pos_of_best = 0;
for (idx, val) in self.iter().enumerate().skip(1) {
if val < &self[pos_of_best] {
pos_of_best = idx;
}
}
pos_of_best
}
fn index_of_max(&self) -> usize {
let mut pos_of_best = 0;
for (idx, val) in self.iter().enumerate().skip(1) {
if val > &self[pos_of_best] {
pos_of_best = idx;
}
}
pos_of_best
}
}
pub fn index_of_min_by<T, F>(n: usize, f: F) -> usize
where
T: PartialOrd,
F: Fn(usize) -> T,
{
assert!(n > 0);
let mut best_idx = 0;
let mut best_val = f(0);
for idx in 1..n {
let cur_val = f(idx);
if cur_val < best_val {
best_val = cur_val;
best_idx = idx;
}
}
best_idx
}
pub fn index_of_max_by<T, F>(n: usize, f: F) -> usize
where
T: PartialOrd,
F: Fn(usize) -> T,
{
assert!(n > 0);
let mut best_idx = 0;
let mut best_val = f(0);
for idx in 1..n {
let cur_val = f(idx);
if cur_val > best_val {
best_val = cur_val;
best_idx = idx;
}
}
best_idx
}
}
pub mod num_traits {
use std::cmp::Ordering;
use std::fmt::Debug;
use std::ops::Add;
use std::ops::AddAssign;
use std::ops::Div;
use std::ops::DivAssign;
use std::ops::Mul;
use std::ops::MulAssign;
use std::ops::Sub;
use std::ops::SubAssign;
pub trait HasConstants<T> {
const MAX: T;
const MIN: T;
const ZERO: T;
const ONE: T;
const TWO: T;
}
pub trait ConvSimple<T> {
fn from_i32(val: i32) -> T;
fn to_i32(self) -> i32;
fn to_f64(self) -> f64;
}
pub trait Signum {
fn signum(&self) -> i32;
}
pub trait Number:
Copy
+ Add<Output = Self>
+ AddAssign
+ Sub<Output = Self>
+ SubAssign
+ Mul<Output = Self>
+ MulAssign
+ Div<Output = Self>
+ DivAssign
+ PartialOrd
+ PartialEq
+ HasConstants<Self>
+ Default
+ Debug
+ Sized
+ ConvSimple<Self>
{
}
impl<
T: Copy
+ Add<Output = Self>
+ AddAssign
+ Sub<Output = Self>
+ SubAssign
+ Mul<Output = Self>
+ MulAssign
+ Div<Output = Self>
+ DivAssign
+ PartialOrd
+ PartialEq
+ HasConstants<Self>
+ Default
+ Debug
+ Sized
+ ConvSimple<Self>,
> Number for T
{
}
macro_rules! has_constants_impl {
($t: ident) => {
impl HasConstants<$t> for $t {
// TODO: remove `std` for new rust version..
const MAX: $t = std::$t::MAX;
const MIN: $t = std::$t::MIN;
const ZERO: $t = 0;
const ONE: $t = 1;
const TWO: $t = 2;
}
impl ConvSimple<$t> for $t {
fn from_i32(val: i32) -> $t {
val as $t
}
fn to_i32(self) -> i32 {
self as i32
}
fn to_f64(self) -> f64 {
self as f64
}
}
};
}
has_constants_impl!(i32);
has_constants_impl!(i64);
has_constants_impl!(i128);
has_constants_impl!(u32);
has_constants_impl!(u64);
has_constants_impl!(u128);
has_constants_impl!(usize);
has_constants_impl!(u8);
impl ConvSimple<Self> for f64 {
fn from_i32(val: i32) -> Self {
val as f64
}
fn to_i32(self) -> i32 {
self as i32
}
fn to_f64(self) -> f64 {
self
}
}
impl HasConstants<Self> for f64 {
const MAX: Self = Self::MAX;
const MIN: Self = -Self::MAX;
const ZERO: Self = 0.0;
const ONE: Self = 1.0;
const TWO: Self = 2.0;
}
impl<T: Number + Ord> Signum for T {
fn signum(&self) -> i32 {
match self.cmp(&T::ZERO) {
Ordering::Greater => 1,
Ordering::Less => -1,
Ordering::Equal => 0,
}
}
}
}
pub mod rec_function {
// Copied from https://github.com/EgorKulikov/rust_algo/blob/master/algo_lib/src/misc/recursive_function.rs
use std::marker::PhantomData;
macro_rules! recursive_function {
($name: ident, $trait: ident, ($($type: ident $arg: ident,)*)) => {
pub trait $trait<$($type, )*Output> {
fn call(&mut self, $($arg: $type,)*) -> Output;
}
pub struct $name<F, $($type, )*Output>
where
F: FnMut(&mut dyn $trait<$($type, )*Output>, $($type, )*) -> Output,
{
f: F,
$($arg: PhantomData<$type>,
)*
phantom_output: PhantomData<Output>,
}
impl<F, $($type, )*Output> $name<F, $($type, )*Output>
where
F: FnMut(&mut dyn $trait<$($type, )*Output>, $($type, )*) -> Output,
{
pub fn new(f: F) -> Self {
Self {
f,
$($arg: Default::default(),
)*
phantom_output: Default::default(),
}
}
}
impl<F, $($type, )*Output> $trait<$($type, )*Output> for $name<F, $($type, )*Output>
where
F: FnMut(&mut dyn $trait<$($type, )*Output>, $($type, )*) -> Output,
{
fn call(&mut self, $($arg: $type,)*) -> Output {
let const_ptr = &self.f as *const F;
let mut_ptr = const_ptr as *mut F;
unsafe { (&mut *mut_ptr)(self, $($arg, )*) }
}
}
}
}
recursive_function!(RecursiveFunction0, Callable0, ());
recursive_function!(RecursiveFunction, Callable, (Arg arg,));
recursive_function!(RecursiveFunction2, Callable2, (Arg1 arg1, Arg2 arg2,));
recursive_function!(RecursiveFunction3, Callable3, (Arg1 arg1, Arg2 arg2, Arg3 arg3,));
recursive_function!(RecursiveFunction4, Callable4, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4,));
recursive_function!(RecursiveFunction5, Callable5, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5,));
recursive_function!(RecursiveFunction6, Callable6, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5, Arg6 arg6,));
recursive_function!(RecursiveFunction7, Callable7, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5, Arg6 arg6, Arg7 arg7,));
recursive_function!(RecursiveFunction8, Callable8, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5, Arg6 arg6, Arg7 arg7, Arg8 arg8,));
recursive_function!(RecursiveFunction9, Callable9, (Arg1 arg1, Arg2 arg2, Arg3 arg3, Arg4 arg4, Arg5 arg5, Arg6 arg6, Arg7 arg7, Arg8 arg8, Arg9 arg9,));
}
pub mod vec_apply_delta {
use crate::algo_lib::misc::num_traits::Number;
pub trait ApplyDelta<T> {
fn add_to_all(self, delta: T) -> Self;
fn sub_from_all(self, sub: T) -> Self;
}
impl<T> ApplyDelta<T> for Vec<T>
where
T: Number,
{
fn add_to_all(mut self, delta: T) -> Self {
self.iter_mut().for_each(|val| *val += delta);
self
}
fn sub_from_all(mut self, sub: T) -> Self {
self.iter_mut().for_each(|val| *val -= sub);
self
}
}
impl<T> ApplyDelta<T> for Vec<(T, T)>
where
T: Number,
{
fn add_to_all(mut self, delta: T) -> Self {
self.iter_mut().for_each(|(val1, val2)| {
*val1 += delta;
*val2 += delta
});
self
}
fn sub_from_all(mut self, sub: T) -> Self {
self.iter_mut().for_each(|(val1, val2)| {
*val1 -= sub;
*val2 -= sub;
});
self
}
}
pub trait ApplyDelta2<T> {
fn add_to_all(&mut self, delta: T);
fn sub_from_all(&mut self, sub: T);
}
impl<T> ApplyDelta2<T> for [T]
where
T: Number,
T: Sized,
{
fn add_to_all(self: &mut [T], delta: T) {
self.iter_mut().for_each(|x| *x += delta);
}
fn sub_from_all(&mut self, sub: T) {
self.iter_mut().for_each(|x| *x -= sub);
}
}
}
}
pub mod seg_trees {
pub mod hld {
use std::ops::Range;
use crate::algo_lib::misc::rec_function::Callable;
use crate::algo_lib::misc::rec_function::Callable3;
use crate::algo_lib::misc::rec_function::RecursiveFunction;
use crate::algo_lib::misc::rec_function::RecursiveFunction3;
pub struct Hld {
parent: Vec<usize>,
pub order: Vec<usize>,
block_start: Vec<usize>,
pos_in_order: Vec<usize>,
}
impl Hld {
pub fn new(mut g: Vec<Vec<usize>>, tree_root: usize) -> Self {
let n = g.len();
let mut size = vec![0; n];
let mut parent = vec![0; n];
RecursiveFunction3::new(|f, v: usize, p: usize, h: usize| {
parent[v] = p;
size[v] = 1;
for &to in g[v].iter() {
if to != p {
f.call(to, v, h + 1);
size[v] += size[to];
}
}
g[v].sort_by(|&u, &v| size[u].cmp(&size[v]).reverse());
})
.call(tree_root, tree_root, 0);
let mut order = vec![];
RecursiveFunction::new(|f, v: usize| {
order.push(v);
for &to in g[v].iter() {
if to != parent[v] {
f.call(to);
}
}
})
.call(tree_root);
let mut pos_in_order = vec![0; n];
for i in 0..n {
pos_in_order[order[i]] = i;
}
let mut block_start = vec![0; n];
for i in 1..n {
if order[i - 1] == parent[order[i]] {
block_start[i] = block_start[i - 1];
} else {
block_start[i] = i;
}
}
Self {
parent,
order,
block_start,
pos_in_order,
}
}
pub fn find_path_segs(&self, mut u: usize, mut v: usize) -> Vec<Range<usize>> {
let mut segs = vec![];
while u != v {
if self.pos_in_order[u] < self.pos_in_order[v] {
std::mem::swap(&mut u, &mut v);
}
let from = std::cmp::max(
self.block_start[self.pos_in_order[u]],
self.pos_in_order[v] + 1,
);
segs.push(from..self.pos_in_order[u] + 1);
u = self.parent[self.order[from]];
}
segs.push(self.pos_in_order[v]..self.pos_in_order[v] + 1);
segs
}
pub fn lca(&self, mut v: usize, mut u: usize) -> usize {
while v != u {
if self.pos_in_order[v] < self.pos_in_order[u] {
std::mem::swap(&mut v, &mut u);
}
if self.block_start[self.pos_in_order[v]] <= self.pos_in_order[u] {
return u;
}
v = self.parent[self.order[self.block_start[self.pos_in_order[v]]]];
}
v
}
}
}
pub mod lazy_seg_tree {
use std::ops::Range;
use crate::algo_lib::seg_trees::seg_tree_trait::SegTreeNode;
///
/// Segment Tree
///
#[allow(unused)]
#[derive(Clone)]
pub struct SegTree<T: SegTreeNode> {
n: usize,
tree: Vec<T>,
updates_to_push: Vec<Option<T::Update>>,
context: T::Context,
right_nodes: Vec<usize>,
}
#[allow(unused)]
impl<T: SegTreeNode> SegTree<T> {
fn pull(&mut self, v: usize, vr: usize) {
self.tree[v] = T::join_nodes(&self.tree[v + 1], &self.tree[vr], &self.context);
}
fn build(&mut self, v: usize, l: usize, r: usize, init_val: &T) {
if l + 1 == r {
self.tree[v] = init_val.clone();
} else {
let m = (l + r) >> 1;
let vr = v + ((m - l) << 1);
self.build(v + 1, l, m, init_val);
self.build(vr, m, r, init_val);
self.pull(v, vr);
}
}
fn push(&mut self, v: usize, l: usize, r: usize) {
let update = self.updates_to_push[v].clone();
self.updates_to_push[v] = None;
match update {
None => {}
Some(update) => {
let m = (l + r) >> 1;
self.apply_update(v + 1, &update, m - l == 1);
self.apply_update(v + ((r - l) & !1), &update, r - m == 1);
}
}
}
fn get_(&mut self, v: usize, l: usize, r: usize, ql: usize, qr: usize) -> T {
assert!(qr >= l);
assert!(ql < r);
if ql <= l && r <= qr {
return self.tree[v].clone();
}
let m = (l + r) >> 1;
let vr = v + ((m - l) << 1);
self.push(v, l, r);
let res = if ql >= m {
self.get_(vr, m, r, ql, qr)
} else if qr <= m {
self.get_(v + 1, l, m, ql, qr)
} else {
T::join_nodes(
&self.get_(v + 1, l, m, ql, qr),
&self.get_(vr, m, r, ql, qr),
&self.context,
)
};
self.pull(v, vr);
res
}
fn join_updates(current: &mut Option<T::Update>, add: &T::Update) {
match current {
None => *current = Some(add.clone()),
Some(current) => T::join_updates(current, add),
};
}
fn apply_update(&mut self, v: usize, update: &T::Update, is_leaf: bool) {
T::apply_update(&mut self.tree[v], update);
if !is_leaf {
Self::join_updates(&mut self.updates_to_push[v], update);
}
}
fn modify_(&mut self, v: usize, l: usize, r: usize, ql: usize, qr: usize, update: &T::Update) {
assert!(qr >= l);
assert!(ql < r);
if ql <= l && r <= qr {
self.apply_update(v, update, r - l == 1);
return;
}
let m = (l + r) >> 1;
let vr = v + ((m - l) << 1);
self.push(v, l, r);
if ql >= m {
self.modify_(vr, m, r, ql, qr, update);
} else if qr <= m {
self.modify_(v + 1, l, m, ql, qr, update);
} else {
self.modify_(v + 1, l, m, ql, qr, update);
self.modify_(vr, m, r, ql, qr, update);
};
self.pull(v, vr);
}
pub fn update(&mut self, range: Range<usize>, update: T::Update) {
if range.is_empty() {
return;
}
assert!(!range.is_empty());
self.modify_(0, 0, self.n, range.start, range.end, &update);
}
pub fn update_point(&mut self, pos: usize, new_node: T) {
let mut l = 0;
let mut r = self.n;
let mut v: usize = 0;
let mut to_pull = vec![];
while r - l > 1 {
let m = (l + r) >> 1;
let vr = v + ((m - l) << 1);
self.push(v, l, r);
to_pull.push((v, vr));
if pos < m {
r = m;
v = v + 1;
} else {
l = m;
v = vr;
}
}
self.tree[v] = new_node;
for (v, vr) in to_pull.into_iter().rev() {
self.pull(v, vr);
}
}
fn find_last_true_(
&mut self,
v: usize,
l: usize,
r: usize,
range: Range<usize>,
f: &impl Fn(&T) -> bool,
) -> Option<usize> {
if range.start >= r || l >= range.end {
return None;
}
let m = (l + r) >> 1;
let vr = v + ((m - l) << 1);
if range.start <= l && r <= range.end {
if !f(&self.tree[v]) {
return None;
}
if r - l == 1 {
return Some(l);
}
}
self.push(v, l, r);
if let Some(res) = self.find_last_true_(vr, m, r, range.clone(), f) {
Some(res)
} else {
self.find_last_true_(v + 1, l, m, range, f)
}
}
// returns position
pub fn find_last_true(&mut self, range: Range<usize>, f: impl Fn(&T) -> bool) -> Option<usize> {
self.find_last_true_(0, 0, self.n, range, &f)
}
pub fn get(&mut self, range: Range<usize>) -> T {
if range.is_empty() {
return T::default();
}
self.get_(0, 0, self.n, range.start, range.end)
}
pub fn new_with_context(n: usize, f: impl Fn(usize) -> T, context: T::Context) -> Self {
assert!(n > 0);
let tree = vec![T::default(); 2 * n - 1];
let updates_to_push = vec![None; 2 * n - 1];
let mut res = SegTree {
n,
tree,
updates_to_push,
context,
right_nodes: vec![],
};
res.build_f(0, 0, n, &f);
res
}
pub fn new(n: usize, f: impl Fn(usize) -> T) -> Self
where
T::Context: Default,
{
assert!(n > 0);
let tree = vec![T::default(); 2 * n - 1];
let updates_to_push = vec![None; 2 * n - 1];
let mut res = SegTree {
n,
tree,
updates_to_push,
context: T::Context::default(),
right_nodes: vec![],
};
res.build_f(0, 0, n, &f);
res
}
fn build_f(&mut self, v: usize, l: usize, r: usize, f: &impl Fn(usize) -> T) {
if l + 1 == r {
self.tree[v] = f(l);
} else {
let m = (l + r) >> 1;
let vr = v + ((m - l) << 1);
self.build_f(v + 1, l, m, f);
self.build_f(vr, m, r, f);
self.pull(v, vr);
}
}
pub fn len(&self) -> usize {
self.n
}
pub fn expert_get_node(&self, node: usize) -> &T {
&self.tree[node]
}
pub fn expert_get_left_node(&self, node: usize) -> usize {
node + 1
}
fn build_right_nodes(&mut self, v: usize, l: usize, r: usize) {
if l + 1 == r {
self.right_nodes.push(0);
} else {
let m = (l + r) >> 1;
let vr = v + ((m - l) << 1);
self.right_nodes.push(vr);
self.build_right_nodes(v + 1, l, m);
self.build_right_nodes(vr, m, r);
}
}
// TODO: shouldn't be mut
pub fn expert_get_right_node(&mut self, node: usize) -> usize {
if self.right_nodes.is_empty() {
self.build_right_nodes(0, 0, self.n);
}
self.right_nodes[node]
}
// Used for Kinetic Seg Tree
pub fn expert_rebuild_nodes(&mut self, should_rebuild: impl Fn(&T, &T::Context) -> bool) {
self.expert_rebuild_nodes_(0, 0, self.n, &should_rebuild);
}
fn expert_rebuild_nodes_(
&mut self,
v: usize,
l: usize,
r: usize,
should_rebuild: &impl Fn(&T, &T::Context) -> bool,
) {
if r - l <= 1 || !should_rebuild(&self.tree[v], &self.context) {
return;
}
let m = (l + r) >> 1;
let vr = v + ((m - l) << 1);
self.push(v, l, r);
self.expert_rebuild_nodes_(v + 1, l, m, should_rebuild);
self.expert_rebuild_nodes_(vr, m, r, should_rebuild);
self.pull(v, vr);
}
pub fn update_context(&mut self, f: impl Fn(&mut T::Context)) {
f(&mut self.context);
}
pub fn get_context(&self) -> &T::Context {
&self.context
}
}
}
pub mod seg_tree_2d {
use std::ops::Range;
use std::ops::RangeInclusive;
use crate::algo_lib::misc::binary_search::binary_search_first_true;
use crate::algo_lib::seg_trees::lazy_seg_tree::SegTree;
use crate::algo_lib::seg_trees::seg_tree_trait::SegTreeNode;
pub struct SegTree2d<T: Ord, U: SegTreeNode> {
all_y: Vec<T>,
tree_y: SegTree<U>,
x_range: RangeInclusive<T>,
mid_x: T,
child: Vec<SegTree2d<T, U>>,
}
impl<T: Ord + Copy, U: SegTreeNode> SegTree2d<T, U> {
pub fn new(pts: Vec<(T, T)>) -> Self
where
U::Context: Default,
{
assert!(!pts.is_empty());
let mut all_x: Vec<T> = pts.iter().map(|&(x, _y)| x).collect();
all_x.sort();
all_x.dedup();
let mut all_y: Vec<T> = pts.iter().map(|&(_x, y)| y).collect();
all_y.sort();
all_y.dedup();
let tree_y = SegTree::new(all_y.len(), |_| U::default());
let mid_x = all_x[all_x.len() / 2];
let mut child = vec![];
if all_x.len() > 1 {
let mut left_pts = vec![];
let mut right_pts = vec![];
for &(x, y) in pts.iter() {
if x < mid_x {
left_pts.push((x, y));
} else {
right_pts.push((x, y));
}
}
assert!(!left_pts.is_empty() && !right_pts.is_empty());
let left = Self::new(left_pts);
let right = Self::new(right_pts);
child.push(left);
child.push(right);
}
Self {
all_y,
tree_y,
mid_x,
child,
x_range: all_x[0]..=all_x[all_x.len() - 1],
}
}
pub fn update(&mut self, x: T, y: T, value: U) {
let y_pos = self.all_y.binary_search(&y).unwrap();
self.tree_y.update_point(y_pos, value.clone());
if !self.child.is_empty() {
if x < self.mid_x {
self.child[0].update(x, y, value);
} else {
self.child[1].update(x, y, value);
}
}
}
pub fn query(&mut self, x_range: Range<T>, y_range: Range<T>) -> U {
let mut res = U::default();
if x_range.start <= *self.x_range.start() && x_range.end > *self.x_range.end() {
let y_start =
binary_search_first_true(0..self.all_y.len(), |p| self.all_y[p] >= y_range.start);
let y_end =
binary_search_first_true(0..self.all_y.len(), |p| self.all_y[p] >= y_range.end);
res = self.tree_y.get(y_start..y_end);
} else if !self.child.is_empty() {
if x_range.start < self.mid_x {
res = U::join_nodes(
&res,
&self.child[0].query(x_range.clone(), y_range.clone()),
self.tree_y.get_context(),
);
}
if x_range.end > self.mid_x {
res = U::join_nodes(
&res,
&self.child[1].query(x_range.clone(), y_range.clone()),
self.tree_y.get_context(),
);
}
}
res
}
}
}
pub mod seg_tree_trait {
pub trait SegTreeNode: Clone + Default {
fn join_nodes(l: &Self, r: &Self, context: &Self::Context) -> Self;
fn apply_update(node: &mut Self, update: &Self::Update);
fn join_updates(current: &mut Self::Update, add: &Self::Update);
type Update: Clone;
type Context;
}
}
}
}
fn main() {
crate::solution::submit();
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 2112kb
input:
4 1 1 2 2 1 2 2 3 2 4
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 2280kb
input:
5 1 3 2 2 1 1 2 2 3 3 4 4 5
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 0ms
memory: 2232kb
input:
6 1 1 2 2 3 3 1 2 2 3 3 4 4 5 5 6
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 0ms
memory: 2292kb
input:
6 1 2 3 4 5 6 1 2 2 3 3 4 4 5 5 6
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3076kb
input:
2000 845 1171 345 282 1181 625 754 289 681 493 423 840 1494 318 266 1267 967 379 135 14 39 191 60 972 116 1216 1205 19 194 185 1360 861 379 430 1262 1151 756 65 389 488 277 53 1283 1438 101 1465 195 714 737 980 80 298 961 1326 163 1163 1317 1152 992 35 334 802 1502 486 710 234 555 88 1278 146 46 696...
output:
5
result:
ok single line: '5'
Test #6:
score: 0
Accepted
time: 783ms
memory: 145636kb
input:
200000 48015 47923 20609 71806 43752 68214 95683 89449 25809 58110 19878 52931 7845 45206 86245 82945 62977 37876 12456 105915 10509 92943 66950 88545 26442 26545 42278 66977 3970 9631 21524 43638 7979 58240 25719 56260 276 89721 9553 16550 52161 30307 82748 108443 36676 48581 59069 57412 62453 7965...
output:
5
result:
ok single line: '5'
Test #7:
score: 0
Accepted
time: 782ms
memory: 145192kb
input:
200000 13011 51198 65374 107045 66506 14385 35784 94265 71449 41817 24646 60714 53382 68358 9354 840 3139 71282 72215 69550 2121 41498 13675 76444 67690 40513 56439 12832 51976 35333 47208 59602 98993 9383 77866 10464 41517 89125 58804 91741 66160 74208 70991 63865 84870 14282 2441 78046 73372 36311...
output:
7
result:
ok single line: '7'
Test #8:
score: 0
Accepted
time: 782ms
memory: 146852kb
input:
200000 38715 33241 65919 39407 27500 36200 2259 42301 79147 57505 20 81399 69499 23658 14534 86934 14352 69558 59763 43318 35360 3281 38188 40058 40571 103709 75625 8434 53802 87159 98628 69421 53711 47986 18350 6079 37362 39377 71936 89573 25983 66882 48999 58918 66432 17453 82515 9588 95375 87287 ...
output:
45
result:
ok single line: '45'
Test #9:
score: 0
Accepted
time: 825ms
memory: 148816kb
input:
200000 36449 57574 3145 38591 832 17710 66613 78947 27635 83275 89878 48329 94614 584 96832 9321 72046 44873 5396 61452 63224 63740 26579 13706 108490 19092 89439 85884 12016 5105 48638 74004 41569 35006 22276 45609 25350 49906 35479 15875 68938 77699 48828 21628 11242 77040 70838 45771 27704 64865 ...
output:
135
result:
ok single line: '135'
Test #10:
score: 0
Accepted
time: 996ms
memory: 154276kb
input:
200000 13528 65006 30352 8565 36687 6748 5507 44320 7189 17847 46996 82728 102722 4727 36914 74228 21460 87970 11733 47170 67282 104558 66436 64504 57055 88619 42995 25569 101298 90984 76491 51994 62257 103424 8221 69668 99170 6808 29043 73058 5277 26614 23654 25152 64939 38418 78518 5330 37531 4305...
output:
425
result:
ok single line: '425'
Test #11:
score: 0
Accepted
time: 1123ms
memory: 161588kb
input:
200000 92279 5566 62695 50240 45387 51097 57743 94873 53220 29260 72584 38043 86335 33441 12946 30267 12932 18258 4560 8896 64393 39608 53183 34285 36518 18501 51940 8658 101018 48522 21336 104735 25785 73132 33489 81905 94563 18128 87872 24765 54563 57218 61869 50458 75919 63764 48155 4489 35212 44...
output:
839
result:
ok single line: '839'
Test #12:
score: 0
Accepted
time: 708ms
memory: 135064kb
input:
200000 96438 84772 88103 81186 60908 116093 94738 28602 35022 91108 60687 75572 100094 50553 58445 117024 96154 53539 23185 112280 90369 32413 95244 11077 91008 109781 6404 2285 3544 111712 49414 10399 113626 81435 11321 52557 17023 113260 14225 66464 61352 98403 36521 110038 57172 42868 68512 69031...
output:
31
result:
ok single line: '31'
Test #13:
score: 0
Accepted
time: 724ms
memory: 137528kb
input:
200000 50750 86282 92049 114579 8296 28675 45880 47381 71400 43379 111535 32316 37104 35968 100241 6914 81284 48969 62890 63486 107557 80178 76322 31515 24682 85646 12681 106054 5167 50339 39004 16152 112081 10605 66750 51623 96332 77287 75452 50609 1549 1652 45229 73171 10015 66323 90164 97491 1007...
output:
8108
result:
ok single line: '8108'
Test #14:
score: 0
Accepted
time: 1014ms
memory: 156144kb
input:
200000 103710 58811 65880 57203 97861 52397 63433 39586 97768 103209 103882 94183 50235 39832 92390 90699 48046 43740 86592 19659 27107 39892 7594 27400 95581 16516 29641 51389 17391 97193 93724 70446 91047 67946 5821 96978 101553 35096 54450 104968 93366 64974 46399 81084 97703 64161 38168 55002 10...
output:
16254
result:
ok single line: '16254'
Test #15:
score: 0
Accepted
time: 705ms
memory: 154908kb
input:
200000 88202 74369 54948 48433 90064 106858 57479 24810 31634 66587 14453 9546 77108 81830 36583 76158 5411 103453 9138 44425 55569 108655 29336 6156 33 78407 12653 61049 89911 48056 85840 41409 60932 69039 50823 604 57680 30956 7683 35427 99677 86508 44657 42731 105490 13120 101415 3024 32965 10326...
output:
4
result:
ok single line: '4'
Test #16:
score: 0
Accepted
time: 711ms
memory: 137196kb
input:
200000 10797 110783 14050 78735 2502 18514 116854 6066 7024 88298 49894 5068 113306 111164 293 38365 84020 117567 109538 103830 69630 28231 107911 18477 95413 78305 59492 112114 12973 20189 93556 49731 50223 69605 54609 74804 42990 28998 22878 45999 93363 7282 71880 49057 46461 94559 53582 109357 25...
output:
6
result:
ok single line: '6'
Test #17:
score: 0
Accepted
time: 930ms
memory: 146420kb
input:
200000 48737 28745 46719 51708 55344 100505 22387 88659 52750 92399 63371 63773 69558 28543 3923 23010 101235 32115 106541 2327 42175 67610 109244 77794 49476 70063 4296 22615 9227 107435 58380 27995 78950 8976 80501 71538 73668 82538 68732 86931 19515 54326 85071 28871 46614 56610 53551 67531 47246...
output:
5
result:
ok single line: '5'
Test #18:
score: 0
Accepted
time: 894ms
memory: 146280kb
input:
200000 26426 62873 30891 26591 23480 10950 50429 4430 25803 27494 14124 45946 2115 72645 23096 45892 34188 62963 63230 4026 19204 52592 84051 81275 101029 63022 83786 69487 46792 97893 25402 11283 50048 59942 53521 52133 12216 16801 24535 31962 102839 71080 53210 8687 6049 56323 74430 81175 55370 64...
output:
5
result:
ok single line: '5'
Test #19:
score: 0
Accepted
time: 861ms
memory: 146724kb
input:
200000 64192 51123 57775 25958 30138 51389 48055 24350 73959 42882 73159 20060 24764 56730 79344 32622 98700 1752 102538 20803 89788 11428 16935 19307 25767 38250 64733 76253 69835 40964 8146 21818 64392 104263 78420 57145 46240 44745 28359 28598 38527 60156 9818 30837 20404 99634 75031 71165 60654 ...
output:
4
result:
ok single line: '4'
Test #20:
score: 0
Accepted
time: 902ms
memory: 146996kb
input:
200000 30875 49873 48854 101512 66585 67679 13806 38786 40598 83034 6738 61701 26783 17734 29228 34850 55071 61098 88072 20496 60333 53325 32602 102521 99956 17288 105589 74068 66276 21670 78040 75943 2292 87380 76885 55439 897 82814 36764 80920 53230 16085 36883 61234 106576 28271 6915 11089 21463 ...
output:
3
result:
ok single line: '3'
Test #21:
score: 0
Accepted
time: 845ms
memory: 147996kb
input:
200000 75618 85661 92814 29954 24466 50323 95886 9384 11050 57981 86917 38495 12021 82933 13692 5285 32566 29306 59046 47309 90373 70494 81527 6001 62574 94496 70347 31615 21329 91026 46255 26717 108227 71208 49245 29004 99849 61951 46547 72596 51712 22511 4844 20109 60399 24412 104182 14880 40185 2...
output:
3
result:
ok single line: '3'