結果
問題 | No.1036 Make One With GCD 2 |
ユーザー |
![]() |
提出日時 | 2020-04-24 21:59:11 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 346 ms / 2,000 ms |
コード長 | 5,661 bytes |
コンパイル時間 | 24,662 ms |
コンパイル使用メモリ | 378,452 KB |
実行使用メモリ | 23,600 KB |
最終ジャッジ日時 | 2024-09-16 13:15:31 |
合計ジャッジ時間 | 32,346 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#![allow(unused)]use kyoproio::*;use std::{collections::*,io::{self, prelude::*},iter,mem::{replace, swap},};fn main() -> io::Result<()> {std::thread::Builder::new().stack_size(64 * 1024 * 1024).spawn(solve)?.join().unwrap();Ok(())}fn solve() {let stdin = io::stdin();let mut kin = KInput::new(stdin.lock());let stdout = io::stdout();let mut out = io::BufWriter::new(stdout.lock());macro_rules! output { ($($args:expr),+) => { write!(&mut out, $($args),+) }; }macro_rules! outputln {($($args:expr),+) => { output!($($args),+); outputln!(); };() => { output!("\n"); if cfg!(debug_assertions) { out.flush(); } }}let n: usize = kin.input();let mut a: Vec<u64> = kin.seq(n);a.push(1);let mut swag = Swag::new(|&x, &y| gcd(x, y));let mut ans = n * (n + 1) / 2;let mut j = 0;for i in 0..n {while j <= n && swag.fold() != Some(1) {swag.push(a[j]);j += 1;}let l = j - i - 1;ans -= l;swag.pop();}outputln!("{}", ans);}fn gcd(mut x: u64, mut y: u64) -> u64 {while y != 0 {x %= y;swap(&mut x, &mut y);}x}pub struct Swag<T, F> {f: F,f_head: Vec<T>,tail: Vec<T>,f_tail: Option<T>,}impl<T: Clone, F: Fn(&T, &T) -> T> Swag<T, F> {pub fn new(f: F) -> Self {Self {f,f_head: Vec::new(),tail: Vec::new(),f_tail: None,}}pub fn push(&mut self, x: T) {self.f_tail = Some(if let Some(y) = self.f_tail.as_ref() {(self.f)(y, &x)} else {x.clone()});self.tail.push(x);}pub fn pop(&mut self) {if self.f_head.is_empty() {for x in self.tail.drain(..).rev() {self.f_head.push(if let Some(y) = self.f_head.last() {(self.f)(&x, y)} else {x});}self.f_tail = None;}self.f_head.pop();}pub fn fold(&self) -> Option<T> {match (self.f_head.last(), self.f_tail.as_ref()) {(Some(x), Some(y)) => Some((self.f)(x, y)),(Some(x), None) => Some(x.clone()),(None, Some(y)) => Some(y.clone()),_ => None,}}pub fn len(&self) -> usize {self.f_head.len() + self.tail.len()}pub fn is_empty(&self) -> bool {self.f_head.is_empty() && self.tail.is_empty()}}// -----------------------------------------------------------------------------pub mod kyoproio {#![warn(unused)]use std::io::prelude::*;pub trait Input {fn str(&mut self) -> &str;fn input<T: InputParse>(&mut self) -> T {T::input(self)}fn iter<T: InputParse>(&mut self) -> Iter<T, Self> {Iter(self, std::marker::PhantomData)}fn seq<T: InputParse, B: std::iter::FromIterator<T>>(&mut self, n: usize) -> B {self.iter().take(n).collect()}}pub struct KInput<R> {src: R,buf: String,pos: usize,}impl<R: BufRead> KInput<R> {pub fn new(src: R) -> Self {Self {src,buf: String::with_capacity(1024),pos: 0,}}}impl<R: BufRead> Input for KInput<R> {fn str(&mut self) -> &str {loop {if self.pos >= self.buf.len() {self.pos = 0;self.buf.clear();if self.src.read_line(&mut self.buf).expect("io error") == 0 {return &self.buf;}}let range = self.pos..self.buf[self.pos..].find(|c: char| c.is_ascii_whitespace()).map(|i| i + self.pos).unwrap_or_else(|| self.buf.len());self.pos = range.end + 1;if range.end > range.start {return &self.buf[range];}}}}pub struct Iter<'a, T, I: ?Sized>(&'a mut I, std::marker::PhantomData<*const T>);impl<'a, T: InputParse, I: Input + ?Sized> Iterator for Iter<'a, T, I> {type Item = T;fn next(&mut self) -> Option<T> {Some(self.0.input())}}pub trait InputParse: Sized {fn input<I: Input + ?Sized>(src: &mut I) -> Self;}impl InputParse for Vec<u8> {fn input<I: Input + ?Sized>(src: &mut I) -> Self {src.str().as_bytes().to_owned()}}macro_rules! from_str_impl {{ $($T:ty)* } => {$(impl InputParse for $T {fn input<I: Input + ?Sized>(src: &mut I) -> Self {src.str().parse::<$T>().expect("parse error")}})*}}from_str_impl! {String char bool f32 f64 isize i8 i16 i32 i64 i128 usize u8 u16 u32 u64 u128}macro_rules! tuple_impl {($H:ident $($T:ident)*) => {impl<$H: InputParse, $($T: InputParse),*> InputParse for ($H, $($T),*) {fn input<I: Input + ?Sized>(src: &mut I) -> Self {($H::input(src), $($T::input(src)),*)}}tuple_impl!($($T)*);};() => {}}tuple_impl!(A B C D E F G);}