結果
| 問題 | No.1011 Infinite Stairs |
| ユーザー |
 へのく
|
| 提出日時 | 2020-06-20 18:08:44 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 209 ms / 2,000 ms |
| コード長 | 41,094 bytes |
| コンパイル時間 | 13,829 ms |
| コンパイル使用メモリ | 393,444 KB |
| 実行使用メモリ | 6,948 KB |
| 最終ジャッジ日時 | 2024-07-17 12:10:51 |
| 合計ジャッジ時間 | 15,369 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,816 KB |
| testcase_01 | AC | 1 ms
6,816 KB |
| testcase_02 | AC | 7 ms
6,948 KB |
| testcase_03 | AC | 136 ms
6,940 KB |
| testcase_04 | AC | 209 ms
6,940 KB |
| testcase_05 | AC | 209 ms
6,944 KB |
| testcase_06 | AC | 1 ms
6,940 KB |
| testcase_07 | AC | 25 ms
6,944 KB |
| testcase_08 | AC | 1 ms
6,944 KB |
| testcase_09 | AC | 1 ms
6,944 KB |
| testcase_10 | AC | 8 ms
6,944 KB |
| testcase_11 | AC | 86 ms
6,944 KB |
| testcase_12 | AC | 5 ms
6,944 KB |
| testcase_13 | AC | 47 ms
6,940 KB |
| testcase_14 | AC | 4 ms
6,940 KB |
| testcase_15 | AC | 29 ms
6,944 KB |
| testcase_16 | AC | 145 ms
6,944 KB |
| testcase_17 | AC | 154 ms
6,944 KB |
| testcase_18 | AC | 62 ms
6,940 KB |
| testcase_19 | AC | 1 ms
6,944 KB |
| testcase_20 | AC | 7 ms
6,944 KB |
| testcase_21 | AC | 34 ms
6,944 KB |
| testcase_22 | AC | 131 ms
6,944 KB |
| testcase_23 | AC | 32 ms
6,944 KB |
| testcase_24 | AC | 30 ms
6,940 KB |
| testcase_25 | AC | 61 ms
6,944 KB |
| testcase_26 | AC | 16 ms
6,944 KB |
ソースコード
#![allow(unused_imports, non_snake_case)]
#![allow(dead_code)]
use crate::scanner::Scanner;
use crate::{data_structure::segment_tree::SegRangeAdd, query::imosm::imos};
modint!();
fn main() {
let mut scan = Scanner::new();
let n = scan.read::<i32>();
let d = scan.read::<i32>();
let k = scan.read::<i32>();
let mut dp = list ! ( Z :: new ( 0 ) ; d * n + 1 );
dp[0] = Z::new(1);
for _ in 0..n {
let mut ranges = list!();
for i in 0..=d * n {
let x = dp[i];
if i + 1 < dp.ilen() {
ranges.push((i + 1..=i + d, x));
}
}
dp = imos(dp.ilen(), &ranges);
}
println!("{}", dp[k]);
}
pub mod data_structure {
pub mod segment_tree {
use crate::ext::range::{IntRangeBounds, RangeEx};
use crate::{arraylist::List, independent::integer::Int};
use std::ops::{Range, RangeBounds};
pub struct SegTree<'a> {
node: List<i64>,
op: Box<dyn Fn(i64, i64) -> i64 + 'a>,
zero: i64,
n: i32,
}
impl<'a> SegTree<'a> {
pub fn new<B>(v: List<i64>, zero: i64, op: B) -> SegTree<'a>
where
B: Fn(i64, i64) -> i64 + 'a,
{
let size = v.ilen();
let mut n = 1i32;
while n < size {
n *= 2
}
let mut node = List::init(zero, 2 * n - 1);
for i in 0..size {
node[i + n - 1] = v[i]
}
for i in (0..n - 1).rev() {
node[i] = op(node[2 * i + 1], node[2 * i + 2])
}
SegTree {
node,
op: Box::new(op),
zero,
n,
}
}
pub fn set(&mut self, mut x: i32, value: i64) {
x += self.n - 1;
self.node[x] = value;
while x > 0 {
x = (x - 1) / 2;
self.node[x] = (self.op)(self.node[2 * x + 1], self.node[2 * x + 2]);
}
}
pub fn get1(&self, i: i32) -> i64 {
self.getrec(i..i + 1, 0, 0..self.n)
}
pub fn get<T>(&self, query: T) -> i64
where
T: RangeBounds<i32>,
{
self.getrec(query.to_harfopen(0, self.n), 0, 0..self.n)
}
fn getrec(&self, query: Range<i32>, k: i32, range: Range<i32>) -> i64 {
if query.separate_range(&range) {
return self.zero;
}
if query.contain_range(&range) {
return self.node[k];
}
let vl = self.getrec(
query.clone(),
2 * k + 1,
range.start..(range.start + range.end) / 2,
);
let vr = self.getrec(
query.clone(),
2 * k + 2,
(range.start + range.end) / 2..range.end,
);
(self.op)(vl, vr)
}
}
pub struct DualSegTree<'a> {
node: List<i64>,
op: Box<dyn Fn(i64, i64) -> i64 + 'a>,
n: i32,
}
impl<'a> DualSegTree<'a> {
pub fn new<B>(v: List<i64>, zero: i64, op: B) -> DualSegTree<'a>
where
B: Fn(i64, i64) -> i64 + 'a,
{
let size = v.ilen();
let mut n = 1i32;
while n < size {
n *= 2
}
let mut node = List::init(zero, 2 * n - 1);
for i in 0..size {
node[i + n - 1] = v[i]
}
for i in (0..n - 1).rev() {
node[i] = op(node[2 * i + 1], node[2 * i + 2])
}
DualSegTree {
node,
op: Box::new(op),
n,
}
}
pub fn get(&self, mut x: i32) -> i64 {
x += self.n - 1;
let mut ret = self.node[x];
while x > 0 {
x = (x - 1) / 2;
ret = (self.op)(ret, self.node[x]);
}
ret
}
pub fn set<T>(&mut self, query: T, value: i64)
where
T: RangeBounds<i32>,
{
let n = self.n;
self.setrec(query.to_harfopen(0, n), 0, 0..n, value);
}
fn setrec(&mut self, query: Range<i32>, k: i32, range: Range<i32>, value: i64) {
if query.separate_range(&range) {
return;
}
if query.contain_range(&range) {
self.node[k] = (self.op)(self.node[k], value);
return;
}
self.setrec(
query.clone(),
2 * k + 1,
range.start..(range.start + range.end) / 2,
value,
);
self.setrec(
query.clone(),
2 * k + 2,
(range.start + range.end) / 2..range.end,
value,
);
}
}
pub struct SegRangeAdd<T> {
node: List<T>,
lazy: List<T>,
n: i32,
}
impl<T: Int> SegRangeAdd<T> {
pub fn new(v: List<T>) -> SegRangeAdd<T> {
let size = v.ilen();
let mut n = 1;
while n < size {
n *= 2
}
let mut node = List::init(T::zero(), 2 * n - 1);
let lazy = List::init(T::zero(), 2 * n - 1);
for i in 0..size {
node[i + n - 1] = v[i]
}
for i in (0..n - 1).rev() {
node[i] = node[i * 2 + 1] + node[i * 2 + 2]
}
SegRangeAdd { node, lazy, n }
}
fn eval(&mut self, k: i32, range: Range<i32>) {
if self.lazy[k] != T::zero() {
let tmp = self.lazy[k];
self.node[k] += tmp;
if range.width() > 1 {
self.lazy[2 * k + 1] += tmp / T::one().next();
self.lazy[2 * k + 2] += tmp / T::one().next();
}
self.lazy[k] = T::zero();
}
}
pub fn add<U>(&mut self, query: U, x: T)
where
U: RangeBounds<i32>,
{
let n = self.n;
self.addrec(query.to_harfopen(0, n), x, 0, 0..n)
}
fn addrec(&mut self, query: Range<i32>, x: T, k: i32, range: Range<i32>) {
self.eval(k, range.clone());
if query.separate_range(&range) {
return;
}
if query.contain_range(&range) {
self.lazy[k] += T::from_i32(range.width()) * x;
self.eval(k, range.clone());
} else {
self.addrec(
query.clone(),
x,
2 * k + 1,
range.start..(range.start + range.end) / 2,
);
self.addrec(
query.clone(),
x,
2 * k + 2,
(range.start + range.end) / 2..range.end,
);
self.node[k] = self.node[2 * k + 1] + self.node[2 * k + 2];
}
}
pub fn sum<U>(&mut self, query: U) -> T
where
U: RangeBounds<i32>,
{
let n = self.n;
self.sumrec(query.to_harfopen(0, n), 0, 0..n)
}
fn sumrec(&mut self, query: Range<i32>, k: i32, range: Range<i32>) -> T {
if query.separate_range(&range) {
return T::zero();
}
self.eval(k, range.clone());
if query.contain_range(&range) {
return self.node[k];
}
let vl = self.sumrec(
query.clone(),
2 * k + 1,
range.start..(range.start + range.end) / 2,
);
let vr = self.sumrec(
query.clone(),
2 * k + 2,
(range.start + range.end) / 2..range.end,
);
vl + vr
}
}
pub struct SegRangeUpdate<'a> {
node: List<i64>,
lazy: List<i64>,
has_lazy: List<bool>,
op: Box<dyn Fn(i64, i64) -> i64 + 'a>,
zero: i64,
n: i32,
}
impl<'a> SegRangeUpdate<'a> {
pub fn new<B>(v: List<i64>, zero: i64, op: B) -> SegRangeUpdate<'a>
where
B: Fn(i64, i64) -> i64 + 'a,
{
let size = v.ilen();
let mut n = 1i32;
while n < size {
n *= 2
}
let mut node = List::init(zero, 2 * n - 1);
let lazy = List::init(0, 2 * n - 1);
let has_lazy = List::init(false, 2 * n - 1);
for i in 0..size {
node[i + n - 1] = v[i]
}
for i in (0..n - 1).rev() {
node[i] = op(node[i * 2 + 1], node[i * 2 + 2])
}
SegRangeUpdate {
node,
lazy,
has_lazy,
op: Box::new(op),
zero,
n,
}
}
fn eval(&mut self, k: i32, range: Range<i32>) {
if self.has_lazy[k] {
self.node[k] = self.lazy[k];
if range.width() > 1 {
self.lazy[2 * k + 1] = self.lazy[k];
self.lazy[2 * k + 2] = self.lazy[k];
self.has_lazy[2 * k + 1] = true;
self.has_lazy[2 * k + 2] = true;
}
self.has_lazy[k] = false;
}
}
pub fn set<T>(&mut self, query: T, x: i64)
where
T: RangeBounds<i32>,
{
let n = self.n;
self.setrec(query.to_harfopen(0, n), x, 0, 0..n)
}
fn setrec(&mut self, query: Range<i32>, x: i64, k: i32, range: Range<i32>) {
self.eval(k, range.clone());
if query.separate_range(&range) {
return;
}
if query.contain_range(&range) {
self.lazy[k] = x;
self.has_lazy[k] = true;
self.eval(k, range.clone());
} else {
self.setrec(
query.clone(),
x,
2 * k + 1,
range.start..(range.start + range.end) / 2,
);
self.setrec(
query.clone(),
x,
2 * k + 2,
(range.start + range.end) / 2..range.end,
);
self.node[k] = (self.op)(self.node[2 * k + 1], self.node[2 * k + 2]);
}
}
pub fn get<T>(&mut self, query: T) -> i64
where
T: RangeBounds<i32>,
{
let n = self.n;
self.getrec(query.to_harfopen(0, n), 0, 0..n)
}
fn getrec(&mut self, query: Range<i32>, k: i32, range: Range<i32>) -> i64 {
if query.separate_range(&range) {
return self.zero;
}
self.eval(k, range.clone());
if query.contain_range(&range) {
return self.node[k];
}
let vl = self.getrec(
query.clone(),
2 * k + 1,
range.start..(range.start + range.end) / 2,
);
let vr = self.getrec(
query.clone(),
2 * k + 2,
(range.start + range.end) / 2..range.end,
);
(self.op)(vl, vr)
}
}
pub struct SegIndexTree<'a> {
node: List<(i64, i32)>,
zero: i64,
op: Box<dyn Fn((i64, i32), (i64, i32)) -> (i64, i32) + 'a>,
n: i32,
}
impl<'a> SegIndexTree<'a> {
pub fn new<B>(v: List<i64>, zero: i64, op: B) -> SegIndexTree<'a>
where
B: Fn((i64, i32), (i64, i32)) -> (i64, i32) + 'a,
{
let size = v.ilen();
let mut n = 1i32;
while n < size {
n *= 2
}
let mut node = List::init((zero, 0), 2 * n - 1);
for i in 0..size {
node[i + n - 1] = (v[i], i)
}
for i in (0..n - 1).rev() {
node[i] = op(node[2 * i + 1], node[2 * i + 2])
}
SegIndexTree {
node: node,
zero: zero,
op: Box::new(op),
n: n,
}
}
pub fn set(&mut self, mut x: i32, value: i64) {
let y = x;
x += self.n - 1;
self.node[x] = (value, y);
while x > 0 {
x = (x - 1) / 2;
self.node[x] = (self.op)(self.node[2 * x + 1], self.node[2 * x + 2]);
}
}
pub fn get1(&self, i: i32) -> (i64, i32) {
self.getrec(i..i + 1, 0, 0..self.n)
}
pub fn get<T>(&self, query: T) -> (i64, i32)
where
T: RangeBounds<i32>,
{
self.getrec(query.to_harfopen(0, self.n), 0, 0..self.n)
}
fn getrec(&self, query: Range<i32>, k: i32, range: Range<i32>) -> (i64, i32) {
if query.separate_range(&range) {
return (self.zero, 0);
}
if query.contain_range(&range) {
return self.node[k];
}
let vl = self.getrec(
query.clone(),
2 * k + 1,
range.start..(range.start + range.end) / 2,
);
let vr = self.getrec(
query.clone(),
2 * k + 2,
(range.start + range.end) / 2..range.end,
);
(self.op)(vl, vr)
}
}
}
}
pub mod modulo {
use crate::independent::integer::Int;
use std::marker::PhantomData;
use std::ops::*;
#[derive(Debug, PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)]
pub struct ModInt<T>(pub i64, PhantomData<*const T>);
impl<T: ConstValue> ModInt<T> {
pub fn new<U: Int>(a: U) -> ModInt<T> {
let x = a.to_i64();
if x < 0 {
ModInt::raw(x % T::M + T::M)
} else if x < T::M {
ModInt::raw(x)
} else {
ModInt::raw(x % T::M)
}
}
pub fn pow<U: Int>(self, x: U) -> Self {
let mut n = x.to_i64();
let mut a = self;
let mut res = Self::raw(1);
while n > 0 {
if n & 1 == 1 {
res *= a;
}
a = a * a;
n >>= 1;
}
res
}
pub fn inv(self) -> Self {
self.pow(T::M - 2)
}
#[inline]
fn raw(x: i64) -> ModInt<T> {
ModInt(x, PhantomData)
}
}
pub trait ConstValue: PartialEq + Eq + Copy + Clone + std::hash::Hash + Ord {
const M: i64;
}
impl<T> std::fmt::Display for ModInt<T> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(f, "{}", self.0)
}
}
macro_rules ! impl_from_for_modint { ( $ ( $ tpe : ident ) ,* ) => { $ ( impl < T : ConstValue > From <$ tpe > for ModInt < T > { fn from ( n : $ tpe ) -> Self { Self :: new ( n ) } } ) * } ; }
impl_from_for_modint!(u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize);
impl<T: ConstValue> Add for ModInt<T> {
type Output = ModInt<T>;
fn add(self, other: ModInt<T>) -> ModInt<T> {
let mut ret = self.0 + other.0;
if ret >= T::M {
ret -= T::M;
}
Self::raw(ret)
}
}
impl<T: ConstValue> AddAssign for ModInt<T> {
fn add_assign(&mut self, other: Self) {
*self = self.add(other);
}
}
impl<T: ConstValue> Sub for ModInt<T> {
type Output = ModInt<T>;
fn sub(self, other: ModInt<T>) -> ModInt<T> {
let mut ret = self.0 + T::M - other.0;
if ret >= T::M {
ret -= T::M
}
Self::raw(ret)
}
}
impl<T: ConstValue> SubAssign for ModInt<T> {
fn sub_assign(&mut self, other: Self) {
*self = self.sub(other);
}
}
impl<T: ConstValue> Mul for ModInt<T> {
type Output = ModInt<T>;
fn mul(self, other: ModInt<T>) -> ModInt<T> {
Self::raw(self.0 * other.0 % T::M)
}
}
impl<T: ConstValue> MulAssign for ModInt<T> {
fn mul_assign(&mut self, other: Self) {
*self = self.mul(other);
}
}
impl<T: ConstValue> Div for ModInt<T> {
type Output = ModInt<T>;
fn div(self, other: ModInt<T>) -> ModInt<T> {
self * other.inv()
}
}
impl<T: ConstValue> DivAssign for ModInt<T> {
fn div_assign(&mut self, other: Self) {
*self = self.div(other);
}
}
impl<T: ConstValue> Rem for ModInt<T> {
type Output = ModInt<T>;
fn rem(self, other: ModInt<T>) -> ModInt<T> {
Self::raw(self.0 % other.0)
}
}
#[macro_export]
macro_rules! modint {
( ) => {
modint!(1000000007);
};
( $ m : expr ) => {
#[derive(Debug, PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)]
pub enum __M {}
impl $crate::modulo::ConstValue for __M {
const M: i64 = $m;
}
#[allow(dead_code)]
type Z = $crate::modulo::ModInt<__M>;
};
}
macro_rules ! impl_integer_functions { ( $ ( $ tofn : ident , $ fromfn : ident , $ tpe : ident ) ,* ) => { $ ( fn $ tofn ( & self ) -> $ tpe { self . 0 as $ tpe } fn $ fromfn ( x : $ tpe ) -> Self { Self :: new ( x ) } ) * } ; }
impl<T: ConstValue> Int for ModInt<T> {
impl_integer_functions!(
to_u8, from_u8, u8, to_u16, from_u16, u16, to_u32, from_u32, u32, to_u64, from_u64,
u64, to_u128, from_u128, u128, to_i8, from_i8, i8, to_i16, from_i16, i16, to_i32,
from_i32, i32, to_i64, from_i64, i64, to_i128, from_i128, i128, to_usize, from_usize,
usize, to_isize, from_isize, isize
);
fn zero() -> Self {
Self::new(0)
}
fn one() -> Self {
Self::new(1)
}
}
}
pub mod ext {
pub mod range {
use crate::independent::integer::Int;
use std::cmp::{max, min};
use std::ops::{Bound, Range, RangeBounds, RangeInclusive};
pub trait RangeEx<T> {
fn width(&self) -> T;
fn empty(&self) -> bool;
fn contain_range(&self, inner: &Self) -> bool;
fn separate_range(&self, other: &Self) -> bool;
type ReturnRange;
fn overlap(&self, other: &Self) -> Self::ReturnRange;
}
impl<T: Int> RangeEx<T> for Range<T> {
fn width(&self) -> T {
if self.empty() {
T::zero()
} else {
self.end - self.start
}
}
fn empty(&self) -> bool {
!(self.start < self.end)
}
fn contain_range(&self, inner: &Self) -> bool {
self.start <= inner.start && inner.end <= self.end
}
fn separate_range(&self, other: &Self) -> bool {
self.end <= other.start || other.end <= self.start
}
type ReturnRange = Range<T>;
fn overlap(&self, other: &Self) -> Self::ReturnRange {
let left = max(self.start, other.start);
let right = min(self.end, other.end);
left..right
}
}
impl<T: Int> RangeEx<T> for RangeInclusive<T> {
fn width(&self) -> T {
if self.empty() {
T::zero()
} else {
*self.end() - *self.start() + T::one()
}
}
fn empty(&self) -> bool {
!(self.start() <= self.end())
}
fn contain_range(&self, inner: &Self) -> bool {
self.start() <= inner.start() && inner.end() <= self.end()
}
fn separate_range(&self, other: &Self) -> bool {
self.end() <= other.start() || other.end() <= self.start()
}
type ReturnRange = RangeInclusive<T>;
fn overlap(&self, other: &Self) -> Self::ReturnRange {
let left = *max(self.start(), other.start());
let right = *min(self.end(), other.end());
left..=right
}
}
pub trait IntRangeBounds<U: Int>: RangeBounds<U> {
#[doc = " inclusive"]
fn lower_bound(&self, lower_bound: U) -> U {
match self.start_bound() {
Bound::Included(x) => max(lower_bound, *x),
Bound::Excluded(x) => max(lower_bound, *x + U::one()),
Bound::Unbounded => lower_bound,
}
}
#[doc = " exclusive"]
fn upper_bound(&self, upper_bound: U) -> U {
match self.end_bound() {
Bound::Included(x) => min(upper_bound, *x + U::one()),
Bound::Excluded(x) => min(upper_bound, *x),
Bound::Unbounded => upper_bound,
}
}
fn to_harfopen(&self, lb: U, ub: U) -> Range<U> {
self.lower_bound(lb)..self.upper_bound(ub)
}
}
impl<T: ?Sized, U: Int> IntRangeBounds<U> for T where T: RangeBounds<U> {}
}
}
pub mod macros {
#[macro_export]
macro_rules ! for_ { ( $ init : stmt ; $ cond : expr ; $ incr : expr , $ body : block ) => { $ init while $ cond { $ body $ incr ; } } ; }
#[macro_export]
macro_rules! chmax {
( $ x : expr , $ y : expr ) => {
if $x < $y {
$x = $y;
true
} else {
false
}
};
}
#[macro_export]
macro_rules! chmin {
( $ x : expr , $ y : expr ) => {
if $x > $y {
$x = $y;
true
} else {
false
}
};
}
#[macro_export]
macro_rules ! min { ( $ a : expr $ ( , ) * ) => { { $ a } } ; ( $ a : expr , $ b : expr $ ( , ) * ) => { { std :: cmp :: min ( $ a , $ b ) } } ; ( $ a : expr , $ ( $ rest : expr ) ,+ $ ( , ) * ) => { { std :: cmp :: min ( $ a , min ! ( $ ( $ rest ) ,+ ) ) } } ; }
#[macro_export]
macro_rules ! max { ( $ a : expr $ ( , ) * ) => { { $ a } } ; ( $ a : expr , $ b : expr $ ( , ) * ) => { { std :: cmp :: max ( $ a , $ b ) } } ; ( $ a : expr , $ ( $ rest : expr ) ,+ $ ( , ) * ) => { { std :: cmp :: max ( $ a , max ! ( $ ( $ rest ) ,+ ) ) } } ; }
#[macro_export]
macro_rules ! assign { ( $ arr : ident $ ( [ $ a : expr ] ) + = $ right : expr ) => { assign ! ( $ arr , $ ( [ $ a ] ) + , = , $ right , default ) ; } ; ( $ arr : ident $ ( [ $ a : expr ] ) + += $ right : expr ) => { assign ! ( $ arr , $ ( [ $ a ] ) + , += , $ right , default ) ; } ; ( $ arr : ident $ ( [ $ a : expr ] ) + -= $ right : expr ) => { assign ! ( $ arr , $ ( [ $ a ] ) + , -= , $ right , default ) ; } ; ( $ arr : ident $ ( [ $ a : expr ] ) + |= $ right : expr ) => { assign ! ( $ arr , $ ( [ $ a ] ) + , |= , $ right , default ) ; } ; ( $ arr : ident $ ( [ $ a : expr ] ) + &= $ right : expr ) => { assign ! ( $ arr , $ ( [ $ a ] ) + , &= , $ right , default ) ; } ; ( $ arr : ident $ ( [ $ a : expr ] ) + ^= $ right : expr ) => { assign ! ( $ arr , $ ( [ $ a ] ) + , ^= , $ right , default ) ; } ; ( $ arr : ident $ ( [ $ a : expr ] ) + min $ right : expr ) => { assign ! ( $ arr , $ ( [ $ a ] ) + , ^= , $ right , min ) ; } ; ( $ arr : ident $ ( [ $ a : expr ] ) + max $ right : expr ) => { assign ! ( $ arr , $ ( [ $ a ] ) + , ^= , $ right , max ) ; } ; ( $ arr : expr , [ $ head : expr ] , $ op : tt , $ right : expr , default ) => { let head = $ head ; if ( 0 ..$ arr . ilen ( ) ) . contains ( &$ head ) { let tmp = $ right ; $ arr [ head ] $ op tmp ; } } ; ( $ arr : expr , [ $ head : expr ] , $ op : tt , $ right : expr , min ) => { let head = $ head ; if ( 0 ..$ arr . ilen ( ) ) . contains ( &$ head ) { let tmp = $ right ; $ arr [ head ] = std :: cmp :: min ( $ arr [ head ] , tmp ) ; } } ; ( $ arr : expr , [ $ head : expr ] , $ op : tt , $ right : expr , max ) => { let head = $ head ; if ( 0 ..$ arr . ilen ( ) ) . contains ( &$ head ) { let tmp = $ right ; $ arr [ head ] = std :: cmp :: max ( $ arr [ head ] , tmp ) ; } } ; ( $ arr : expr , [ $ head : expr ] $ ( [ $ a : expr ] ) +, $ op : tt , $ right : expr , $ kind : ident ) => { let head = $ head ; if ( 0 ..$ arr . ilen ( ) ) . contains ( &$ head ) { assign ! ( $ arr [ head ] , $ ( [ $ a ] ) +, $ op , $ right , $ kind ) ; } } ; }
#[macro_export]
macro_rules! unwrap {
( $ arg : expr ) => {{
let tmp = $arg;
if tmp.is_none() {
return;
}
tmp.unwrap()
}};
}
#[macro_export]
macro_rules! swap {
( $ a : expr , $ b : expr ) => {
let tmp = $a;
$a = $b;
$b = tmp;
};
}
}
pub mod independent {
pub mod integer {
pub trait Int:
std::ops::Add<Output = Self>
+ std::ops::Sub<Output = Self>
+ std::ops::Mul<Output = Self>
+ std::ops::Div<Output = Self>
+ std::ops::Rem<Output = Self>
+ std::ops::AddAssign
+ std::ops::SubAssign
+ std::ops::MulAssign
+ std::ops::DivAssign
+ std::hash::Hash
+ PartialEq
+ Eq
+ PartialOrd
+ Ord
+ Copy
{
fn to_u8(&self) -> u8;
fn to_u16(&self) -> u16;
fn to_u32(&self) -> u32;
fn to_u64(&self) -> u64;
fn to_u128(&self) -> u128;
fn to_i8(&self) -> i8;
fn to_i16(&self) -> i16;
fn to_i32(&self) -> i32;
fn to_i64(&self) -> i64;
fn to_i128(&self) -> i128;
fn to_usize(&self) -> usize;
fn to_isize(&self) -> isize;
fn from_u8(x: u8) -> Self;
fn from_u16(x: u16) -> Self;
fn from_u32(x: u32) -> Self;
fn from_u64(x: u64) -> Self;
fn from_u128(x: u128) -> Self;
fn from_i8(x: i8) -> Self;
fn from_i16(x: i16) -> Self;
fn from_i32(x: i32) -> Self;
fn from_i64(x: i64) -> Self;
fn from_i128(x: i128) -> Self;
fn from_usize(x: usize) -> Self;
fn from_isize(x: isize) -> Self;
fn zero() -> Self;
fn one() -> Self;
fn next(&self) -> Self {
*self + Self::one()
}
}
macro_rules ! impl_integer_functions { ( $ selftpe : ident , $ ( $ tofn : ident , $ fromfn : ident , $ tpe : ident ) ,* ) => { $ ( fn $ tofn ( & self ) -> $ tpe { * self as $ tpe } fn $ fromfn ( x : $ tpe ) -> Self { x as $ selftpe } ) * } ; }
macro_rules ! impl_integer { ( $ ( $ tpe : ident ) ,* ) => { $ ( impl Int for $ tpe { impl_integer_functions ! ( $ tpe , to_u8 , from_u8 , u8 , to_u16 , from_u16 , u16 , to_u32 , from_u32 , u32 , to_u64 , from_u64 , u64 , to_u128 , from_u128 , u128 , to_i8 , from_i8 , i8 , to_i16 , from_i16 , i16 , to_i32 , from_i32 , i32 , to_i64 , from_i64 , i64 , to_i128 , from_i128 , i128 , to_usize , from_usize , usize , to_isize , from_isize , isize ) ; fn zero ( ) -> Self { 0 } fn one ( ) -> Self { 1 } } ) * } ; }
impl_integer!(u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize);
}
}
pub mod query {
pub mod imosm {
use crate::arraylist::List;
use crate::{ext::range::IntRangeBounds, independent::integer::Int};
use std::ops::RangeBounds;
pub fn imos<T: RangeBounds<i32>, I: Int>(n: i32, ranges: &List<(T, I)>) -> List<I> {
let mut ret = List::init(I::zero(), n);
for (r, d) in ranges.iter().map(|r| (r.0.to_harfopen(0, n), r.1)) {
ret[r.start] += d;
if r.end < n {
ret[r.end] -= d;
}
}
for i in 0..n {
if i > 0 {
ret[i] = ret[i] + ret[i - 1];
}
}
ret
}
}
}
pub mod scanner {
use crate::arraylist::List;
use std::io::{stdin, BufReader, Bytes, Read, Stdin};
use std::str::FromStr;
pub struct Scanner {
buf: Bytes<BufReader<Stdin>>,
}
impl Scanner {
pub fn new() -> Scanner {
Scanner {
buf: BufReader::new(stdin()).bytes(),
}
}
pub fn read_next<T: FromStr>(&mut self) -> Option<T> {
let token = self
.buf
.by_ref()
.map(|c| c.unwrap() as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect::<String>();
token.parse::<T>().ok()
}
pub fn read<T: FromStr>(&mut self) -> T {
self.read_next().unwrap()
}
pub fn readn<T: FromStr>(&mut self, n: i32) -> List<T> {
(0..n).map(|_| self.read::<T>()).collect()
}
pub fn chars(&mut self) -> List<char> {
self.read::<String>().chars().collect()
}
}
}
pub mod arraylist {
use crate::{ext::range::IntRangeBounds, independent::integer::Int};
use std::fmt::Formatter;
use std::iter::FromIterator;
use std::ops::{Index, IndexMut, RangeBounds};
use std::slice::Iter;
#[derive(Clone, PartialEq, Eq)]
pub struct List<T> {
pub vec: Vec<T>,
}
impl<T> List<T> {
#[inline]
pub fn new() -> List<T> {
List { vec: vec![] }
}
#[inline]
pub fn init(init: T, n: i32) -> List<T>
where
T: Clone,
{
List {
vec: vec![init; n as usize],
}
}
#[inline]
pub fn from_vec(vec: Vec<T>) -> List<T> {
List { vec }
}
#[inline]
pub fn ilen(&self) -> i32 {
self.vec.len() as i32
}
#[inline]
pub fn iter(&self) -> Iter<'_, T> {
self.vec.iter()
}
#[inline]
pub fn push(&mut self, item: T) {
self.vec.push(item);
}
#[inline]
pub fn sort(&mut self)
where
T: Ord,
{
self.vec.sort();
}
#[inline]
pub fn reverse(&mut self) {
self.vec.reverse();
}
#[inline]
pub fn sort_by<F>(&mut self, compare: F)
where
F: FnMut(&T, &T) -> std::cmp::Ordering,
{
self.vec.sort_by(compare)
}
#[inline]
pub fn sort_by_key<K, F>(&mut self, compare: F)
where
F: FnMut(&T) -> K,
K: Ord,
{
self.vec.sort_by_key(compare)
}
#[inline]
pub fn first(&self) -> Option<&T> {
self.vec.first()
}
#[inline]
pub fn last(&self) -> Option<&T> {
self.vec.last()
}
#[inline]
pub fn pop(&mut self) -> Option<T> {
self.vec.pop()
}
#[inline]
pub fn swap(&mut self, i: i32, j: i32) {
self.vec.swap(i as usize, j as usize);
}
#[inline]
pub fn append(&mut self, mut other: Self) {
self.vec.append(&mut other.vec);
}
#[inline]
pub fn extend(&mut self, other: impl Iterator<Item = T>) {
self.vec.extend(other);
}
#[inline]
pub fn mirror(&self) -> std::iter::Cloned<Iter<T>>
where
T: Clone,
{
self.iter().cloned()
}
#[inline]
pub fn map<B, F>(&self, f: F) -> List<B>
where
T: Clone,
F: FnMut(T) -> B,
{
self.mirror().map(f).collect()
}
#[inline]
pub fn filter<P>(&self, predicate: P) -> List<T>
where
T: Clone,
P: FnMut(&T) -> bool,
{
self.mirror().filter(predicate).collect()
}
#[inline]
pub fn filter_map<B, F>(&self, f: F) -> List<B>
where
T: Clone,
F: FnMut(T) -> Option<B>,
{
self.mirror().filter_map(f).collect()
}
#[inline]
pub fn any<P>(&self, predicate: P) -> bool
where
P: FnMut(&T) -> bool,
{
self.iter().any(predicate)
}
#[inline]
pub fn all<P>(&self, predicate: P) -> bool
where
P: FnMut(&T) -> bool,
{
self.iter().all(predicate)
}
#[inline]
pub fn sum(&self) -> T
where
T: Int,
{
self.iter().cloned().fold(T::zero(), |acc, x| acc + x)
}
#[inline]
pub fn enumerate(&self) -> List<(i32, T)>
where
T: Clone,
{
self.mirror()
.enumerate()
.map(|p| (p.0 as i32, p.1))
.collect()
}
#[inline]
pub fn find<P>(&self, mut predicate: P) -> Option<&T>
where
P: FnMut(&T) -> bool,
{
self.iter().find(|x| predicate(*x))
}
#[inline]
pub fn index_of<P>(&self, mut predicate: P) -> Option<i32>
where
P: FnMut(&T) -> bool,
{
self.iter()
.enumerate()
.find(|&(_i, x)| predicate(x))
.map(|p| p.0 as i32)
}
#[inline]
pub fn to<B: FromIterator<T>>(&self) -> B
where
T: Clone,
{
self.mirror().collect()
}
#[inline]
pub fn min(&self) -> Option<&T>
where
T: Ord,
{
self.iter().min()
}
#[inline]
pub fn max(&self) -> Option<&T>
where
T: Ord,
{
self.iter().max()
}
#[inline]
pub fn argmin(&self) -> Option<i32>
where
T: Ord,
{
let item = self.iter().min()?;
self.iter()
.enumerate()
.find(|p| p.1 == item)
.map(|p| p.0 as i32)
}
#[inline]
pub fn argmax(&self) -> Option<i32>
where
T: Ord,
{
let item = self.iter().max()?;
self.iter()
.enumerate()
.find(|p| p.1 == item)
.map(|p| p.0 as i32)
}
#[inline]
pub fn part<U>(&self, range: U) -> List<T>
where
T: Clone,
U: RangeBounds<i32>,
{
List::from_vec(
self.vec[range.lower_bound(0) as usize..range.upper_bound(self.ilen()) as usize]
.to_vec(),
)
}
#[inline]
pub fn first_exn(&self) -> &T {
self.first().unwrap()
}
#[inline]
pub fn last_exn(&self) -> &T {
self.last().unwrap()
}
#[inline]
pub fn pop_exn(&mut self) -> T {
self.pop().unwrap()
}
#[inline]
pub fn min_exn(&self) -> &T
where
T: Ord,
{
self.min().unwrap()
}
#[inline]
pub fn max_exn(&self) -> &T
where
T: Ord,
{
self.max().unwrap()
}
#[inline]
pub fn argmin_exn(&self) -> i32
where
T: Ord,
{
self.argmin().unwrap()
}
#[inline]
pub fn argmax_exn(&self) -> i32
where
T: Ord,
{
self.argmax().unwrap()
}
#[inline]
pub fn find_exn<P>(&self, predicate: P) -> &T
where
P: FnMut(&T) -> bool,
{
self.find(predicate).unwrap()
}
#[inline]
pub fn index_of_exn<P>(&self, predicate: P) -> i32
where
P: FnMut(&T) -> bool,
{
self.index_of(predicate).unwrap()
}
}
impl<T> Index<i32> for List<T> {
type Output = T;
#[inline]
fn index(&self, index: i32) -> &Self::Output {
if cfg!(debug_assertions) {
self.vec.index(index as usize)
} else {
unsafe { self.vec.get_unchecked(index as usize) }
}
}
}
impl<T> IndexMut<i32> for List<T> {
#[inline]
fn index_mut(&mut self, index: i32) -> &mut Self::Output {
if cfg!(debug_assertions) {
self.vec.index_mut(index as usize)
} else {
unsafe { self.vec.get_unchecked_mut(index as usize) }
}
}
}
impl<T> FromIterator<T> for List<T> {
fn from_iter<U: IntoIterator<Item = T>>(iter: U) -> Self {
let mut vec = vec![];
for i in iter {
vec.push(i);
}
List { vec }
}
}
impl<T> IntoIterator for List<T> {
type Item = T;
type IntoIter = std::vec::IntoIter<T>;
fn into_iter(self) -> std::vec::IntoIter<T> {
self.vec.into_iter()
}
}
impl<'a, T> IntoIterator for &'a List<T> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Iter<'a, T> {
self.vec.iter()
}
}
impl<T: std::fmt::Display> std::fmt::Display for List<T> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(
f,
"{}",
self.iter()
.map(|x| format!("{}", x))
.collect::<Vec<_>>()
.join(" ")
)
}
}
impl<T: std::fmt::Debug> std::fmt::Debug for List<T> {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
write!(
f,
"[{}]",
self.iter()
.map(|x| format!("{:?}", x))
.collect::<Vec<_>>()
.join(", ")
)
}
}
impl<T> From<Vec<T>> for List<T> {
fn from(vec: Vec<T>) -> Self {
Self::from_vec(vec)
}
}
impl<T: Clone> From<&[T]> for List<T> {
fn from(slice: &[T]) -> Self {
slice.iter().cloned().collect()
}
}
#[macro_export]
macro_rules ! list { ( ) => { $ crate :: arraylist :: List :: new ( ) } ; ( $ v : expr ; $ a : expr ) => { $ crate :: arraylist :: List :: init ( $ v , $ a ) } ; ( $ v : expr ; $ a : expr ; $ ( $ rest : expr ) ;+ ) => { $ crate :: arraylist :: List :: init ( list ! ( $ v ; $ ( $ rest ) ;+ ) , $ a ) } ; }
}