結果
問題 | No.489 株に挑戦 |
ユーザー |
|
提出日時 | 2017-02-26 00:13:43 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 44 ms / 1,000 ms |
コード長 | 4,070 bytes |
コンパイル時間 | 14,403 ms |
コンパイル使用メモリ | 378,340 KB |
実行使用メモリ | 8,576 KB |
最終ジャッジ日時 | 2024-07-19 23:31:11 |
合計ジャッジ時間 | 16,410 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
コンパイルメッセージ
warning: unused macro definition: `trace` --> src/main.rs:7:14 | 7 | macro_rules! trace { | ^^^^^ | = note: `#[warn(unused_macros)]` on by default warning: unused macro definition: `swap` --> src/main.rs:12:14 | 12 | macro_rules! swap { (b:expr) => ({ let t = b = a = t; }) } | ^^^^ warning: variable `k` is assigned to, but never used --> src/main.rs:17:32 | 17 | let mut m = 1; let mut k = 1; | ^ | = note: consider using `_k` instead = note: `#[warn(unused_variables)]` on by default warning: methods `update`, `add`, and `at` are never used --> src/main.rs:60:8 | 14 | impl RMQ { | -------- methods in this implementation ... 60 | fn update(&mut self, idx: usize, x: i64) { | ^^^^^^ ... 71 | fn add(&mut self, idx: usize, x: i64) { | ^^^ ... 76 | fn at(&self, idx: usize) -> i64 { | ^^ | = note: `#[warn(dead_code)]` on by default
ソースコード
#![allow(unused_imports)]use std::io::{ self, Write };use std::str::FromStr;use std::cmp::{ min, max };use std::collections::{ BinaryHeap, VecDeque };macro_rules! trace {($var:expr) => ({let _ = writeln!(&mut std::io::stderr(), ">>> {} = {:?}", stringify!($var), $var);})}macro_rules! swap { ($a:expr, $b:expr) => ({ let t = $b; $b = $a; $a = t; }) }struct RMQ {heap: Vec<i64>, size: usize, lefts: Vec<usize>, rights: Vec<usize>}impl RMQ {fn alignment(n: usize) -> usize {let mut m = 1; let mut k = 1;while n > m { k += 1; m *= 2; }m * 2 - 1}fn of_left(idx: usize, base: usize) -> usize {let mut i = idx; while i < base { i = i * 2 + 1; }i - base}fn of_right(idx: usize, base: usize) -> usize {let mut i = idx; while i < base { i = i * 2 + 2; }i - base}fn new(v: &Vec<i64>) -> RMQ {let n = v.len();let size = RMQ::alignment(n);let mut heap = vec![0; size];for i in 0..n { heap[i + size/2] = v[i]; }for i in (0..size/2).rev() { heap[i] = max(heap[i*2+1], heap[i*2+2]); }let lefts = (0..size).map(|i| RMQ::of_left(i, size/2)).collect();let rights = (0..size).map(|i| RMQ::of_right(i, size/2)).collect();RMQ {heap: heap, size: size, lefts: lefts, rights: rights}}// max [left..right] inclusivelyfn max(&self, left: usize, right: usize) -> i64 {if left > right { return 0 }if left == right { return self.heap[self.size/2 + left] }let mut i = self.size/2 + left;loop {let parent = (i - 1) / 2;if self.lefts[parent] == left && self.rights[parent] <= right {i = parent;} else {break}}max(self.heap[i], self.max(self.rights[i] + 1, right))}// [idx] <- xfn update(&mut self, idx: usize, x: i64) {let mut i = idx + self.size/2;self.heap[i] = x;loop {i = (i - 1) / 2;if i == 0 { break }self.heap[i] = max(self.heap[i*2+1], self.heap[i*2+2]);}}// [idx] <- [idx] + xfn add(&mut self, idx: usize, x: i64) {let z = self.heap[idx + self.size/2] + x;self.update(idx, z);}fn at(&self, idx: usize) -> i64 {self.heap[idx + self.size/2]}}fn main() {let mut sc = Scanner::new();let n: usize = sc.cin();let d: usize = sc.cin();let k: i64 = sc.cin();let xs = (0..n).map(|_| sc.cin()).collect::<Vec<i64>>();let rmq = RMQ::new(&xs);let mut ans = 0;let mut a = 0;for i in 0..(n-1) {let mx = rmq.max(i + 1, min(i + d, n - 1));let p = mx - xs[i];if ans < p {ans = p;a = i;}}println!("{}", ans * k);if ans > 0 {for j in (a+1)..n {if ans == xs[j] - xs[a] {println!("{} {}", a, j);break;}}}}#[allow(dead_code)]struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }#[allow(dead_code)]impl Scanner {fn new() -> Scanner { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }fn reserve(&mut self) {while self.buffer.len() == 0 {let mut line = String::new();let _ = self.stdin.read_line(&mut line);for w in line.split_whitespace() {self.buffer.push_back(String::from(w));}}}fn cin<T: FromStr>(&mut self) -> T {self.reserve();match self.buffer.pop_front().unwrap().parse::<T>() {Ok(a) => a,Err(_) => panic!("parse err")}}fn get_char(&mut self) -> char {self.reserve();let head = self.buffer[0].chars().nth(0).unwrap();let tail = String::from( &self.buffer[0][1..] );if tail.len()>0 { self.buffer[0]=tail } else { self.buffer.pop_front(); }head}}