結果
| 問題 | No.901 K-ary εxtrεεmε |
| ユーザー |
 Haar
|
| 提出日時 | 2024-10-14 20:07:30 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 280 ms / 3,000 ms |
| コード長 | 27,504 bytes |
| コンパイル時間 | 15,192 ms |
| コンパイル使用メモリ | 379,516 KB |
| 実行使用メモリ | 51,844 KB |
| 最終ジャッジ日時 | 2024-10-14 20:07:58 |
| 合計ジャッジ時間 | 22,307 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 81 ms
51,844 KB |
| testcase_01 | AC | 1 ms
5,248 KB |
| testcase_02 | AC | 2 ms
5,248 KB |
| testcase_03 | AC | 2 ms
5,248 KB |
| testcase_04 | AC | 2 ms
5,248 KB |
| testcase_05 | AC | 2 ms
5,248 KB |
| testcase_06 | AC | 2 ms
5,248 KB |
| testcase_07 | AC | 268 ms
46,784 KB |
| testcase_08 | AC | 221 ms
46,640 KB |
| testcase_09 | AC | 205 ms
46,768 KB |
| testcase_10 | AC | 207 ms
46,772 KB |
| testcase_11 | AC | 197 ms
46,740 KB |
| testcase_12 | AC | 216 ms
46,756 KB |
| testcase_13 | AC | 192 ms
46,760 KB |
| testcase_14 | AC | 195 ms
46,880 KB |
| testcase_15 | AC | 199 ms
46,760 KB |
| testcase_16 | AC | 193 ms
46,880 KB |
| testcase_17 | AC | 205 ms
46,856 KB |
| testcase_18 | AC | 232 ms
46,640 KB |
| testcase_19 | AC | 217 ms
46,836 KB |
| testcase_20 | AC | 198 ms
46,852 KB |
| testcase_21 | AC | 198 ms
46,856 KB |
| testcase_22 | AC | 176 ms
46,756 KB |
| testcase_23 | AC | 191 ms
46,744 KB |
| testcase_24 | AC | 280 ms
46,756 KB |
| testcase_25 | AC | 194 ms
46,756 KB |
| testcase_26 | AC | 188 ms
46,756 KB |
| testcase_27 | AC | 145 ms
46,944 KB |
| testcase_28 | AC | 152 ms
46,936 KB |
| testcase_29 | AC | 151 ms
46,948 KB |
コンパイルメッセージ
warning: field `size` is never read
--> src/main.rs:382:13
|
381 | pub struct HLD {
| --- field in this struct
382 | size: usize,
| ^^^^
|
= note: `HLD` has derived impls for the traits `Debug` and `Clone`, but these are intentionally ignored during dead code analysis
= note: `#[warn(dead_code)]` on by default
ソースコード
// Bundled at 2024/10/14 20:05:11 +09:00
// Author: Haar
pub mod main {
use super::*;
use haar_lib::algebra::sum::*;
use haar_lib::ds::segtree::*;
use haar_lib::tree::{auxiliary_tree::*, hld::*, *};
#[allow(unused_imports)]
use haar_lib::{get, input, iter::join_str::*, utils::fastio::*};
#[allow(unused_imports)]
use std::cell::{Cell, RefCell};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet};
#[allow(unused_imports)]
use std::io::Write;
#[allow(unused_imports)]
use std::rc::Rc;
#[derive(Clone, Default)]
pub struct Problem {}
impl Problem {
pub fn main(&mut self) -> Result<(), Box<dyn std::error::Error>> {
let mut io = FastIO::new();
let n = io.read_usize();
let mut builder = TreeBuilder::new(n);
for _ in 0..n - 1 {
let u = io.read_usize();
let v = io.read_usize();
let w = io.read_u64();
builder.extend(Some(TreeEdge::new(u, v, w, ())));
}
let tree = builder.build();
let monoid = Sum::<u64>::new();
let aux = AuxiliaryTree::new(&tree, 0);
let hld = HLD::new(tree.clone(), 0);
let mut seg = Segtree::new(n, monoid);
for e in tree.nodes_iter().flat_map(|a| a.neighbors()) {
if e.from() < e.to() {
seg.update(hld.get_edge_id(e.from(), e.to()).unwrap(), e.weight());
}
}
let q = io.read_usize();
for _ in 0..q {
let k = io.read_usize();
let x = get!(io, [usize; k]);
let x = aux.build(x, |a, b| hld.lca(a, b));
let k = x.len();
let mut ans = 0;
for i in 0..k {
for (l, r) in hld.path_query_edge(x[i], x[(i + 1) % k]) {
ans += seg.fold(l..r);
}
}
ans /= 2;
io.writeln(ans);
}
Ok(())
}
}
}
fn main() {
main::Problem::default().main().unwrap();
}
use crate as haar_lib;
pub mod algebra {
pub mod traits {
pub trait AlgeStruct {
type Output;
}
pub trait BinaryOp: AlgeStruct {
fn op(&self, _: Self::Output, _: Self::Output) -> Self::Output;
}
pub trait Identity: AlgeStruct {
fn id(&self) -> Self::Output;
}
pub trait Inverse: AlgeStruct {
fn inv(&self, _: Self::Output) -> Self::Output;
}
pub trait Commutative {}
pub trait Associative {}
pub trait Idempotence {}
pub trait Semigroup: BinaryOp + Associative {}
impl<T: BinaryOp + Associative> Semigroup for T {}
pub trait Monoid: Semigroup + Identity {}
impl<T: Semigroup + Identity> Monoid for T {}
pub trait AbelianMonoid: Monoid + Commutative {}
impl<T: Monoid + Commutative> AbelianMonoid for T {}
pub trait Group: Monoid + Inverse {}
impl<T: Monoid + Inverse> Group for T {}
pub trait AbelianGroup: Group + Commutative {}
impl<T: Group + Commutative> AbelianGroup for T {}
pub trait Times<T: Clone>: BinaryOp<Output = T> + Identity {
fn times(&self, mut a: Self::Output, mut n: u64) -> Self::Output {
let mut ret = self.id();
while n > 0 {
if n & 1 == 1 {
ret = self.op(ret, a.clone());
}
a = self.op(a.clone(), a);
n >>= 1;
}
ret
}
}
impl<T: Clone, A: BinaryOp<Output = T> + Identity> Times<T> for A {}
}
pub mod sum {
pub use crate::algebra::traits::*;
use crate::impl_algebra;
use std::marker::PhantomData;
#[derive(Clone, Copy, Default, Debug, PartialEq, Eq)]
pub struct Sum<T>(PhantomData<T>);
impl<T> Sum<T> {
pub fn new() -> Self {
Self(PhantomData)
}
}
impl<T> AlgeStruct for Sum<T> {
type Output = T;
}
impl_algebra!(Sum<i8>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: i8| -a, commu: {}, assoc: {});
impl_algebra!(Sum<i16>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: i16| -a, commu: {}, assoc: {});
impl_algebra!(Sum<i32>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: i32| -a, commu: {}, assoc: {});
impl_algebra!(Sum<i64>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: i64| -a, commu: {}, assoc: {});
impl_algebra!(Sum<i128>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: i128| -a, commu: {}, assoc: {});
impl_algebra!(Sum<isize>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: isize| -a, commu: {}, assoc: {});
impl_algebra!(Sum<u8>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
impl_algebra!(Sum<u16>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
impl_algebra!(Sum<u32>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
impl_algebra!(Sum<u64>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
impl_algebra!(Sum<u128>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
impl_algebra!(Sum<usize>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
impl_algebra!(Sum<f32>, op: |_, a, b| a + b, id: |_| 0.0, inv: |_, a: f32| -a, commu: {}, assoc: {});
impl_algebra!(Sum<f64>, op: |_, a, b| a + b, id: |_| 0.0, inv: |_, a: f64| -a, commu: {}, assoc: {});
}
}
pub mod ds {
pub mod segtree {
pub use crate::algebra::traits::Monoid;
use crate::utils::range::range_bounds_to_range;
use std::ops::{Index, RangeBounds};
#[derive(Clone)]
pub struct Segtree<M: Monoid> {
original_size: usize,
size: usize,
data: Vec<M::Output>,
monoid: M,
}
impl<T: Clone, M: Monoid<Output = T>> Segtree<M> {
pub fn new(n: usize, monoid: M) -> Self {
let size = n.next_power_of_two() * 2;
Segtree {
original_size: n,
size,
data: vec![monoid.id(); size],
monoid,
}
}
pub fn fold<R: RangeBounds<usize>>(&self, range: R) -> T {
let (l, r) = range_bounds_to_range(range, 0, self.size / 2);
let mut ret_l = self.monoid.id();
let mut ret_r = self.monoid.id();
let mut l = l + self.size / 2;
let mut r = r + self.size / 2;
while l < r {
if r & 1 == 1 {
r -= 1;
ret_r = self.monoid.op(self.data[r].clone(), ret_r);
}
if l & 1 == 1 {
ret_l = self.monoid.op(ret_l, self.data[l].clone());
l += 1;
}
r >>= 1;
l >>= 1;
}
self.monoid.op(ret_l, ret_r)
}
pub fn assign(&mut self, i: usize, value: T) {
let mut i = i + self.size / 2;
self.data[i] = value;
while i > 1 {
i >>= 1;
self.data[i] = self
.monoid
.op(self.data[i << 1].clone(), self.data[i << 1 | 1].clone());
}
}
pub fn update(&mut self, i: usize, value: T) {
self.assign(
i,
self.monoid.op(self.data[i + self.size / 2].clone(), value),
);
}
}
impl<T: Clone, M: Monoid<Output = T>> From<&Segtree<M>> for Vec<T> {
fn from(from: &Segtree<M>) -> Vec<T> {
from.data[from.size / 2..from.size / 2 + from.original_size].to_vec()
}
}
impl<M: Monoid> Index<usize> for Segtree<M> {
type Output = M::Output;
fn index(&self, i: usize) -> &Self::Output {
&self.data[self.size / 2 + i]
}
}
}
}
pub mod iter {
pub mod join_str {
pub trait JoinStr: Iterator {
fn join_str(self, s: &str) -> String
where
Self: Sized,
Self::Item: ToString,
{
self.map(|x| x.to_string()).collect::<Vec<_>>().join(s)
}
}
impl<I> JoinStr for I where I: Iterator + ?Sized {}
}
}
pub mod macros {
pub mod impl_algebra {
#[macro_export]
macro_rules! impl_algebra {
(@bound $t:ty, op: $f:expr; $($bound:tt)+) => {
impl <$($bound)+> BinaryOp for $t {
fn op(&self, a: Self::Output, b: Self::Output) -> Self::Output {
$f(&self, a, b)
}
}
};
(@nobound $t:ty, op: $f:expr) => {
impl BinaryOp for $t {
fn op(&self, a: Self::Output, b: Self::Output) -> Self::Output {
$f(&self, a, b)
}
}
};
(@bound $t:ty, id: $f:expr; $($bound:tt)+) => {
impl<$($bound)+> Identity for $t {
fn id(&self) -> Self::Output {
$f(&self)
}
}
};
(@nobound $t:ty, id: $f:expr) => {
impl Identity for $t {
fn id(&self) -> Self::Output {
$f(&self)
}
}
};
(@bound $t:ty, inv: $f:expr; $($bound:tt)+) => {
impl<$($bound)+> Inverse for $t {
fn inv(&self, a: Self::Output) -> Self::Output {
$f(self, a)
}
}
};
(@nobound $t:ty, inv: $f:expr) => {
impl Inverse for $t {
fn inv(&self, a: Self::Output) -> Self::Output {
$f(self, a)
}
}
};
(@bound $t:ty, commu: $f:expr; $($bound:tt)+) => {impl<$($bound)+> Commutative for $t {}};
(@nobound $t:ty, commu: $f:expr) => {impl Commutative for $t {}};
(@bound $t:ty, assoc: $f:expr; $($bound:tt)+) => {impl<$($bound)+> Associative for $t {}};
(@nobound $t:ty, assoc: $f:expr) => {impl Associative for $t {}};
(@bound $t:ty, idem: $f:expr; $($bound:tt)+) => {impl<$($bound)+> Idempotence for $t {}};
(@nobound $t:ty, idem: $f:expr) => {impl Idempotence for $t {}};
(const $a:ident : $b:ty; $t:ty, $($s:ident: $f:expr),+) => {
$(impl_algebra!(@bound $t, $s: $f; const $a: $b);)+
};
($a:ident; $t:ty, $($s:ident: $f:expr),+) => {
$(impl_algebra!(@bound $t, $s: $f; $a);)+
};
($t:ty, $($s:ident: $f:expr),+) => {
$(impl_algebra!(@nobound $t, $s: $f);)+
};
}
}
pub mod io {
#[macro_export]
macro_rules! get {
( $in:ident, [$a:tt $(as $to:ty)*; $num:expr] ) => {
{
let n = $num;
(0 .. n).map(|_| get!($in, $a $(as $to)*)).collect::<Vec<_>>()
}
};
( $in:ident, ($($type:tt $(as $to:ty)*),*) ) => {
($(get!($in, $type $(as $to)*)),*)
};
( $in:ident, i8 ) => { $in.read_i64() as i8 };
( $in:ident, i16 ) => { $in.read_i64() as i16 };
( $in:ident, i32 ) => { $in.read_i64() as i32 };
( $in:ident, i64 ) => { $in.read_i64() };
( $in:ident, isize ) => { $in.read_i64() as isize };
( $in:ident, u8 ) => { $in.read_u64() as u8 };
( $in:ident, u16 ) => { $in.read_u64() as u16 };
( $in:ident, u32 ) => { $in.read_u64() as u32 };
( $in:ident, u64 ) => { $in.read_u64() };
( $in:ident, usize ) => { $in.read_u64() as usize };
( $in:ident, [char] ) => { $in.read_chars() };
( $in:ident, $from:tt as $to:ty ) => { <$to>::from(get!($in, $from)) };
}
#[macro_export]
macro_rules! input {
( @inner $in:ident, mut $name:ident : $type:tt ) => {
let mut $name = get!($in, $type);
};
( @inner $in:ident, mut $name:ident : $type:tt as $to:ty ) => {
let mut $name = get!($in, $type as $to);
};
( @inner $in:ident, $name:ident : $type:tt ) => {
let $name = get!($in, $type);
};
( @inner $in:ident, $name:ident : $type:tt as $to:ty ) => {
let $name = get!($in, $type as $to);
};
( $in:ident >> $($($names:ident)* : $type:tt $(as $to:ty)*),* ) => {
$(input!(@inner $in, $($names)* : $type $(as $to)*);)*
}
}
}
}
pub mod tree {
pub mod auxiliary_tree {
use crate::tree::*;
pub struct AuxiliaryTree {
preorder: Vec<usize>,
}
impl AuxiliaryTree {
pub fn new<E: TreeEdgeTrait>(tree: &Tree<E>, root: usize) -> Self {
let n = tree.len();
let mut this = Self {
preorder: vec![0; n],
};
this.dfs(&tree, root, None, &mut 0);
this
}
fn dfs<E: TreeEdgeTrait>(
&mut self,
tree: &Tree<E>,
cur: usize,
par: Option<usize>,
i: &mut usize,
) {
self.preorder[cur] = *i;
*i += 1;
for e in tree.nodes[cur].neighbors() {
if Some(e.to()) != par {
self.dfs(tree, e.to(), Some(cur), i);
}
}
}
pub fn build<F>(&self, mut vs: Vec<usize>, f: F) -> Vec<usize>
where
F: Fn(usize, usize) -> usize,
{
vs.sort_by(|&a, &b| self.preorder[a].cmp(&self.preorder[b]));
let n = vs.len();
for i in 0..n - 1 {
let x = f(vs[i], vs[i + 1]);
vs.push(x);
}
vs.sort_by(|&a, &b| self.preorder[a].cmp(&self.preorder[b]));
vs.dedup();
vs
}
}
}
pub mod hld {
use crate::tree::*;
use std::cmp::max;
#[derive(Clone, Debug)]
pub struct HLD {
size: usize,
par: Vec<Option<usize>>,
head: Vec<usize>,
id: Vec<usize>,
rid: Vec<usize>,
next: Vec<Option<usize>>,
end: Vec<usize>,
}
impl HLD {
pub fn new<E: TreeEdgeTrait>(tree: Tree<E>, root: usize) -> Self {
let size = tree.len();
let mut ret = Self {
size,
par: vec![None; size],
head: vec![0; size],
id: vec![0; size],
rid: vec![0; size],
next: vec![None; size],
end: vec![0; size],
};
let mut tr = vec![vec![]; size];
for (i, nodes) in tree.nodes.iter().enumerate() {
for e in nodes.neighbors() {
tr[i].push(e.to());
}
}
ret.dfs_sub(&mut tr, root, None, &mut vec![1; size]);
ret.dfs_build(&tr, root, &mut 0);
ret
}
fn dfs_sub(
&mut self,
tree: &mut [Vec<usize>],
cur: usize,
par: Option<usize>,
sub: &mut Vec<usize>,
) {
self.par[cur] = par;
tree[cur].retain(|&x| Some(x) != par);
let mut t = 0;
let n = tree[cur].len();
for i in 0..n {
let to = tree[cur][i];
self.dfs_sub(tree, to, Some(cur), sub);
sub[cur] += sub[to];
if sub[to] > t {
t = sub[to];
self.next[cur] = Some(to);
tree[cur].swap(i, 0);
}
}
}
fn dfs_build(&mut self, tree: &[Vec<usize>], cur: usize, index: &mut usize) {
self.id[cur] = *index;
self.rid[*index] = cur;
*index += 1;
for (i, &to) in tree[cur].iter().enumerate() {
self.head[to] = if i == 0 { self.head[cur] } else { to };
self.dfs_build(tree, to, index);
}
self.end[cur] = *index;
}
pub fn path_query_vertex(&self, mut x: usize, mut y: usize) -> Vec<(usize, usize)> {
let mut ret = vec![];
loop {
if self.id[x] > self.id[y] {
std::mem::swap(&mut x, &mut y);
}
ret.push((max(self.id[self.head[y]], self.id[x]), self.id[y] + 1));
if self.head[x] == self.head[y] {
break;
}
y = self.par[self.head[y]].unwrap();
}
ret
}
pub fn path_query_edge(&self, mut x: usize, mut y: usize) -> Vec<(usize, usize)> {
let mut ret = vec![];
loop {
if self.id[x] > self.id[y] {
std::mem::swap(&mut x, &mut y);
}
if self.head[x] == self.head[y] {
if x != y {
ret.push((self.id[x] + 1, self.id[y] + 1));
}
break;
}
ret.push((self.id[self.head[y]], self.id[y] + 1));
y = self.par[self.head[y]].unwrap();
}
ret
}
pub fn subtree_query_vertex(&self, x: usize) -> (usize, usize) {
(self.id[x], self.end[x])
}
pub fn subtree_query_edge(&self, x: usize) -> (usize, usize) {
(self.id[x] + 1, self.end[x])
}
pub fn parent(&self, x: usize) -> Option<usize> {
self.par[x]
}
pub fn get_id(&self, x: usize) -> usize {
self.id[x]
}
pub fn get_edge_id(&self, u: usize, v: usize) -> Option<usize> {
if self.par[u] == Some(v) {
Some(self.id[u])
} else if self.par[v] == Some(u) {
Some(self.id[v])
} else {
None
}
}
pub fn lca(&self, mut u: usize, mut v: usize) -> usize {
loop {
if self.id[u] > self.id[v] {
std::mem::swap(&mut u, &mut v);
}
if self.head[u] == self.head[v] {
return u;
}
v = self.par[self.head[v]].unwrap();
}
}
}
}
pub trait TreeEdgeTrait {
type Weight;
fn from(&self) -> usize;
fn to(&self) -> usize;
fn weight(&self) -> Self::Weight;
fn rev(self) -> Self;
}
#[derive(Clone, Debug)]
pub struct TreeEdge<T, I> {
pub from: usize,
pub to: usize,
pub weight: T,
pub index: I,
}
impl<T, I> TreeEdge<T, I> {
pub fn new(from: usize, to: usize, weight: T, index: I) -> Self {
Self {
from,
to,
weight,
index,
}
}
}
impl<T: Clone, I> TreeEdgeTrait for TreeEdge<T, I> {
type Weight = T;
#[inline]
fn from(&self) -> usize {
self.from
}
#[inline]
fn to(&self) -> usize {
self.to
}
#[inline]
fn weight(&self) -> Self::Weight {
self.weight.clone()
}
fn rev(mut self) -> Self {
std::mem::swap(&mut self.from, &mut self.to);
self
}
}
#[derive(Clone, Debug, Default)]
pub struct TreeNode<E> {
pub parent: Option<E>,
pub children: Vec<E>,
}
impl<E: TreeEdgeTrait> TreeNode<E> {
pub fn neighbors(&self) -> impl DoubleEndedIterator<Item = &E> {
self.children.iter().chain(self.parent.iter())
}
pub fn neighbors_size(&self) -> usize {
self.children.len() + self.parent.as_ref().map_or(0, |_| 1)
}
}
pub struct TreeBuilder<E> {
nodes: Vec<TreeNode<E>>,
}
impl<E: TreeEdgeTrait + Clone> TreeBuilder<E> {
pub fn new(size: usize) -> Self {
Self {
nodes: vec![
TreeNode {
parent: None,
children: vec![],
};
size
],
}
}
pub fn extend(&mut self, edges: impl IntoIterator<Item = E>) {
for e in edges {
self.nodes[e.from()].children.push(e.clone());
self.nodes[e.to()].children.push(e.rev());
}
}
pub fn build(self) -> Tree<E> {
Tree {
nodes: self.nodes,
root: None,
}
}
}
pub struct RootedTreeBuilder<E> {
nodes: Vec<TreeNode<E>>,
root: usize,
}
impl<E: TreeEdgeTrait + Clone> RootedTreeBuilder<E> {
pub fn new(size: usize, root: usize) -> Self {
Self {
nodes: vec![
TreeNode {
parent: None,
children: vec![],
};
size
],
root,
}
}
pub fn extend(&mut self, edges: impl IntoIterator<Item = E>) {
for e in edges {
assert!(self.nodes[e.to()].parent.is_none());
self.nodes[e.from()].children.push(e.clone());
self.nodes[e.to()].parent.replace(e.rev());
}
}
pub fn build(self) -> Tree<E> {
Tree {
nodes: self.nodes,
root: Some(self.root),
}
}
}
#[derive(Clone, Debug)]
pub struct Tree<E> {
nodes: Vec<TreeNode<E>>,
root: Option<usize>,
}
impl<E> Tree<E> {
pub fn nodes_iter(&self) -> impl Iterator<Item = &TreeNode<E>> {
self.nodes.iter()
}
pub fn nodes(&self, i: usize) -> &TreeNode<E> {
&self.nodes[i]
}
pub fn len(&self) -> usize {
self.nodes.len()
}
pub fn is_empty(&self) -> bool {
self.nodes.is_empty()
}
pub fn root(&self) -> Option<usize> {
self.root
}
}
}
pub mod utils {
pub mod fastio {
use std::fmt::Display;
use std::io::{Read, Write};
pub struct FastIO {
in_bytes: Vec<u8>,
in_cur: usize,
out_buf: std::io::BufWriter<std::io::Stdout>,
}
impl FastIO {
pub fn new() -> Self {
let mut s = vec![];
std::io::stdin().read_to_end(&mut s).unwrap();
let cout = std::io::stdout();
Self {
in_bytes: s,
in_cur: 0,
out_buf: std::io::BufWriter::new(cout),
}
}
#[inline]
pub fn getc(&mut self) -> Option<u8> {
if self.in_cur < self.in_bytes.len() {
self.in_cur += 1;
Some(self.in_bytes[self.in_cur])
} else {
None
}
}
#[inline]
pub fn peek(&self) -> Option<u8> {
if self.in_cur < self.in_bytes.len() {
Some(self.in_bytes[self.in_cur])
} else {
None
}
}
#[inline]
pub fn skip(&mut self) {
while self.peek().map_or(false, |c| c.is_ascii_whitespace()) {
self.in_cur += 1;
}
}
pub fn read_u64(&mut self) -> u64 {
self.skip();
let mut ret: u64 = 0;
while self.peek().map_or(false, |c| c.is_ascii_digit()) {
ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as u64;
self.in_cur += 1;
}
ret
}
pub fn read_u32(&mut self) -> u32 {
self.read_u64() as u32
}
pub fn read_usize(&mut self) -> usize {
self.read_u64() as usize
}
pub fn read_i64(&mut self) -> i64 {
self.skip();
let mut ret: i64 = 0;
let minus = if self.peek() == Some(b'-') {
self.in_cur += 1;
true
} else {
false
};
while self.peek().map_or(false, |c| c.is_ascii_digit()) {
ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as i64;
self.in_cur += 1;
}
if minus {
ret = -ret;
}
ret
}
pub fn read_i32(&mut self) -> i32 {
self.read_i64() as i32
}
pub fn read_isize(&mut self) -> isize {
self.read_i64() as isize
}
pub fn read_f64(&mut self) -> f64 {
self.read_chars()
.into_iter()
.collect::<String>()
.parse()
.unwrap()
}
pub fn read_chars(&mut self) -> Vec<char> {
self.skip();
let mut ret = vec![];
while self.peek().map_or(false, |c| c.is_ascii_graphic()) {
ret.push(self.in_bytes[self.in_cur] as char);
self.in_cur += 1;
}
ret
}
pub fn write<T: Display>(&mut self, s: T) {
self.out_buf.write_all(format!("{}", s).as_bytes()).unwrap();
}
pub fn writeln<T: Display>(&mut self, s: T) {
self.write(s);
self.out_buf.write_all(&[b'\n']).unwrap();
}
}
impl Drop for FastIO {
fn drop(&mut self) {
self.out_buf.flush().unwrap();
}
}
}
pub mod range {
use std::ops::RangeBounds;
pub fn range_bounds_to_range<R: RangeBounds<usize>>(
r: R,
start: usize,
end: usize,
) -> (usize, usize) {
use std::ops::Bound::*;
let l = match r.start_bound() {
Included(&l) => l,
Excluded(&l) => l + 1,
Unbounded => start,
}
.max(start);
let r = match r.end_bound() {
Included(&r) => r + 1,
Excluded(&r) => r,
Unbounded => end,
}
.min(end);
(l, r)
}
}
}