結果
問題 | No.905 Sorted? |
ユーザー |
|
提出日時 | 2019-10-11 21:44:52 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 195 ms / 2,000 ms |
コード長 | 7,160 bytes |
コンパイル時間 | 11,500 ms |
コンパイル使用メモリ | 389,324 KB |
実行使用メモリ | 9,472 KB |
最終ジャッジ日時 | 2024-11-25 07:08:14 |
合計ジャッジ時間 | 14,758 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
コンパイルメッセージ
warning: unused variable: `out` --> src/main.rs:104:13 | 104 | let mut out = BufWriter::new(out.lock()); | ^^^ help: if this is intentional, prefix it with an underscore: `_out` | = note: `#[warn(unused_variables)]` on by default warning: variable does not need to be mutable --> src/main.rs:104:9 | 104 | let mut out = BufWriter::new(out.lock()); | ----^^^ | | | help: remove this `mut` | = note: `#[warn(unused_mut)]` on by default warning: variable `N` should have a snake case name --> src/main.rs:107:9 | 107 | N:usize, | ^ help: convert the identifier to snake case: `n` | = note: `#[warn(non_snake_case)]` on by default warning: variable `Q` should have a snake case name --> src/main.rs:109:9 | 109 | Q:usize, | ^ help: convert the identifier to snake case: `q`
ソースコード
#[doc = " https://github.com/hatoo/competitive-rust-snippets"]#[allow(unused_imports)]use std::cmp::{max, min, Ordering};#[allow(unused_imports)]use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};#[allow(unused_imports)]use std::io::{stdin, stdout, BufWriter, Write};#[allow(unused_imports)]use std::iter::FromIterator;#[macro_export]macro_rules ! dvec { ( $ t : expr ; $ len : expr ) => { vec ! [ $ t ; $ len ] } ; ( $ t : expr ; $ len : expr , $ ( $ rest : expr ) ,* ) => { vec ! [dvec ! ( $ t ; $ ( $ rest ) ,* ) ; $ len ] } ; }#[allow(unused_macros)]macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } }#[macro_export]macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut parser = Parser :: from_str ( $ s ) ; input_inner ! { parser , $ ( $ r) * } } ; ( parser = $ parser : ident , $ ( $ r : tt ) * ) => { input_inner ! { $ parser , $ ( $ r ) * } } ; ( new_stdin_parser = $ parser :ident , $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let reader = std :: io :: BufReader :: new ( stdin . lock ( ) ) ; let mut $parser = Parser :: new ( reader ) ; input_inner ! { $ parser , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { input ! { new_stdin_parser = parser ,$ ( $ r ) * } } ; }#[macro_export]macro_rules ! input_inner { ( $ parser : ident ) => { } ; ( $ parser : ident , ) => { } ; ( $ parser : ident , $ var : ident : $ t : tt $ ( $ r : tt) * ) => { let $ var = read_value ! ( $ parser , $ t ) ; input_inner ! { $ parser $ ( $ r ) * } } ; }#[macro_export]macro_rules ! read_value { ( $ parser : ident , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ parser , $ t ) ) ,* ) } ; ( $ parser : ident , [$ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ parser , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ parser :ident , chars ) => { read_value ! ( $ parser , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ parser : ident , usize1 ) => {read_value ! ( $ parser , usize ) - 1 } ; ( $ parser : ident , $ t : ty ) => { $ parser . next ::<$ t > ( ) . expect ( "Parse error" ) } ; }use std::io;use std::io::BufRead;use std::str;pub struct Parser<R> {reader: R,buf: Vec<u8>,pos: usize,}impl Parser<io::Empty> {pub fn from_str(s: &str) -> Parser<io::Empty> {Parser {reader: io::empty(),buf: s.as_bytes().to_vec(),pos: 0,}}}impl<R: BufRead> Parser<R> {pub fn new(reader: R) -> Parser<R> {Parser {reader: reader,buf: vec![],pos: 0,}}pub fn update_buf(&mut self) {self.buf.clear();self.pos = 0;loop {let (len, complete) = {let buf2 = self.reader.fill_buf().unwrap();self.buf.extend_from_slice(buf2);let len = buf2.len();if len == 0 {break;}(len, buf2[len - 1] <= 0x20)};self.reader.consume(len);if complete {break;}}}pub fn next<T: str::FromStr>(&mut self) -> Result<T, T::Err> {loop {let mut begin = self.pos;while begin < self.buf.len() && (self.buf[begin] <= 0x20) {begin += 1;}let mut end = begin;while end < self.buf.len() && (self.buf[end] > 0x20) {end += 1;}if begin != self.buf.len() {self.pos = end;return str::from_utf8(&self.buf[begin..end]).unwrap().parse::<T>();} else {self.update_buf();}}}}#[allow(unused_macros)]macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } }#[doc = " https://github.com/hatoo/competitive-rust-snippets"]const BIG_STACK_SIZE: bool = true;#[allow(dead_code)]fn main() {use std::thread;if BIG_STACK_SIZE {thread::Builder::new().stack_size(32 * 1024 * 1024).name("solve".into()).spawn(solve).unwrap().join().unwrap();} else {solve();}}fn solve() {let out = stdout();let mut out = BufWriter::new(out.lock());input!{N:usize,a:[i64;N],Q:usize,lr: [(usize,usize);Q]}let mut inc = vec![false; N-1];for i in 0..N-1 {if a[i]<=a[i+1] {inc[i]=true;}}let mut dec = vec![false; N-1];for i in 0..N-1 {if a[i]>=a[i+1] {dec[i]=true;}}let mut seg_inc: SEG<MIN> = SEG::new(N-1);let mut seg_dec: SEG<MIN> = SEG::new(N-1);for i in 0..N-1 {if inc[i] {seg_inc.update(i, 1);} else {seg_inc.update(i, 0);}}for i in 0..N-1 {if dec[i] {seg_dec.update(i, 1);} else {seg_dec.update(i, 0);}}for i in 0..Q {let (l,r) = lr[i];if l==r {println!("1 1");} else {let min_inc = seg_inc.query(l,r);let min_dec = seg_dec.query(l,r);println!("{} {}", min_inc, min_dec);}}}#[allow(dead_code)]pub trait Monoid {type T: Clone;fn id() -> Self::T;fn op(a: &Self::T, b: &Self::T) -> Self::T;}#[allow(dead_code)]pub struct SEG<M: Monoid> {n: usize,buf: Vec<M::T>,}impl<M: Monoid> SEG<M> {#[allow(dead_code)]pub fn new(n: usize) -> SEG<M> {let mut m = 1;while m < n {m *= 2;}SEG {n: m,buf: vec![M::id().clone(); 2 * m - 1],}}#[allow(dead_code)]pub fn update(&mut self, k: usize, a: M::T) {let mut k = k + self.n - 1;self.buf[k] = a;while k > 0 {k = (k - 1) / 2;self.buf[k] = M::op(&self.buf[k * 2 + 1], &self.buf[k * 2 + 2]);}}#[allow(dead_code)]pub fn get(&self, k: usize) -> M::T {self.buf[k + self.n].clone()}pub fn do_query(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> M::T {if r <= a || b <= l {return M::id();}if a <= l && r <= b {return self.buf[k].clone();} else {let vl = self.do_query(a, b, k * 2 + 1, l, (l + r) / 2);let vr = self.do_query(a, b, k * 2 + 2, (l + r) / 2, r);return M::op(&vl, &vr);}}#[allow(dead_code)]pub fn query(&self, a: usize, b: usize) -> M::T {self.do_query(a, b, 0, 0, self.n)}}#[allow(dead_code)]struct MIN;impl Monoid for MIN {type T = i64;fn id() -> Self::T {1}fn op(a: &Self::T, b: &Self::T) -> Self::T {std::cmp::min(*a, *b)}}