結果
問題 | No.1021 Children in Classrooms |
ユーザー |
![]() |
提出日時 | 2020-06-21 07:28:36 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 23,223 bytes |
コンパイル時間 | 12,554 ms |
コンパイル使用メモリ | 403,536 KB |
実行使用メモリ | 19,276 KB |
最終ジャッジ日時 | 2024-07-03 17:47:46 |
合計ジャッジ時間 | 15,391 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#![allow(unused_imports, non_snake_case)]#![allow(dead_code)]use crate::query::cumulare::Cumulare;use crate::scanner::Scanner;fn main() {let mut scan = Scanner::new();let n = scan.read::<i32>();let m = scan.read::<i32>();let a = scan.readn::<i64>(n);let s = scan.chars();let mut left = 0;let mut right = n - 1;let mut b = 0;let mut j = 0;for i in 0..m {if s[i] == 'L' {b += 1;chrange!(b, ..=n - 1);chmax!(left, b);if left > right {left = right;}j -= 1;chrange!(j, 0..);} else {b -= 1;chrange!(b, -n + 1..);chmin!(right, n - 1 + b);if right < left {right = left;}j += 1;chrange!(j, ..=n - 1);}}let mut ret = list ! ( 0 ; n );let ca = Cumulare::new(&a);if left == right {ret[j] = ca.sum(..);} else {ret[j] = ca.sum(..=left);ret[j + right - left] = ca.sum(right..);}for i in 0..right - left - 1 {ret[i + j + 1] = a[left + 1 + i];}println!("{}", ret);}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>whereT: 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)whereT: Ord,{self.vec.sort();}#[inline]pub fn reverse(&mut self) {self.vec.reverse();}#[inline]pub fn sort_by<F>(&mut self, compare: F)whereF: FnMut(&T, &T) -> std::cmp::Ordering,{self.vec.sort_by(compare)}#[inline]pub fn sort_by_key<K, F>(&mut self, compare: F)whereF: 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>>whereT: Clone,{self.iter().cloned()}#[inline]pub fn map<B, F>(&self, f: F) -> List<B>whereT: Clone,F: FnMut(T) -> B,{self.mirror().map(f).collect()}#[inline]pub fn filter<P>(&self, predicate: P) -> List<T>whereT: Clone,P: FnMut(&T) -> bool,{self.mirror().filter(predicate).collect()}#[inline]pub fn filter_map<B, F>(&self, f: F) -> List<B>whereT: Clone,F: FnMut(T) -> Option<B>,{self.mirror().filter_map(f).collect()}#[inline]pub fn any<P>(&self, predicate: P) -> boolwhereP: FnMut(&T) -> bool,{self.iter().any(predicate)}#[inline]pub fn all<P>(&self, predicate: P) -> boolwhereP: FnMut(&T) -> bool,{self.iter().all(predicate)}#[inline]pub fn sum(&self) -> TwhereT: Int,{self.iter().cloned().fold(T::zero(), |acc, x| acc + x)}#[inline]pub fn enumerate(&self) -> List<(i32, T)>whereT: Clone,{self.mirror().enumerate().map(|p| (p.0 as i32, p.1)).collect()}#[inline]pub fn find<P>(&self, mut predicate: P) -> Option<&T>whereP: FnMut(&T) -> bool,{self.iter().find(|x| predicate(*x))}#[inline]pub fn index_of<P>(&self, mut predicate: P) -> Option<i32>whereP: 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) -> BwhereT: Clone,{self.mirror().collect()}#[inline]pub fn min(&self) -> Option<&T>whereT: Ord,{self.iter().min()}#[inline]pub fn max(&self) -> Option<&T>whereT: Ord,{self.iter().max()}#[inline]pub fn argmin(&self) -> Option<i32>whereT: 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>whereT: 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>whereT: 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) -> &TwhereT: Ord,{self.min().unwrap()}#[inline]pub fn max_exn(&self) -> &TwhereT: Ord,{self.max().unwrap()}#[inline]pub fn argmin_exn(&self) -> i32whereT: Ord,{self.argmin().unwrap()}#[inline]pub fn argmax_exn(&self) -> i32whereT: Ord,{self.argmax().unwrap()}#[inline]pub fn find_exn<P>(&self, predicate: P) -> &TwhereP: FnMut(&T) -> bool,{self.find(predicate).unwrap()}#[inline]pub fn index_of_exn<P>(&self, predicate: P) -> i32whereP: 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 ) } ; }}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 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! chrange {( $ x : expr , $ r : expr ) => {{let r = $r;match std::ops::RangeBounds::start_bound(&r) {std::ops::Bound::Included(x) => {$crate::chmax!($x, *x);}std::ops::Bound::Excluded(x) => {$crate::chmax!($x, *x + 1);}_ => (),}match std::ops::RangeBounds::end_bound(&r) {std::ops::Bound::Included(x) => {$crate::chmin!($x, *x);}std::ops::Bound::Excluded(x) => {$crate::chmin!($x, *x - 1);}_ => (),}}};}#[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 query {pub mod cumulare {use crate::arraylist::List;use crate::{ext::range::IntRangeBounds, independent::integer::Int};use std::ops::RangeBounds;#[derive(Debug)]pub struct Cumulare<T> {pub s: List<T>,n: i32,}impl<T: Int> Cumulare<T> {pub fn new(a: &List<T>) -> Cumulare<T> {let mut s = List::init(T::zero(), a.ilen() + 1);for i in 0..a.ilen() {s[i + 1] = s[i] + a[i];}Cumulare { s, n: a.ilen() }}#[doc = " [l,r)"]pub fn sum<U>(&self, range: U) -> TwhereU: RangeBounds<i32>,{let r = range.to_harfopen(0, self.n);self.s[r.end] - self.s[r.start]}}}}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()}}}