結果
問題 | No.1332 Range Nearest Query |
ユーザー | Strorkis |
提出日時 | 2021-01-09 19:53:34 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 300 ms / 2,500 ms |
コード長 | 4,964 bytes |
コンパイル時間 | 5,172 ms |
コンパイル使用メモリ | 157,588 KB |
実行使用メモリ | 27,088 KB |
最終ジャッジ日時 | 2023-08-11 16:50:43 |
合計ジャッジ時間 | 18,978 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,384 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 254 ms
18,060 KB |
testcase_04 | AC | 256 ms
17,968 KB |
testcase_05 | AC | 255 ms
18,064 KB |
testcase_06 | AC | 108 ms
26,764 KB |
testcase_07 | AC | 107 ms
26,776 KB |
testcase_08 | AC | 110 ms
26,772 KB |
testcase_09 | AC | 108 ms
26,788 KB |
testcase_10 | AC | 106 ms
26,760 KB |
testcase_11 | AC | 107 ms
26,772 KB |
testcase_12 | AC | 108 ms
26,764 KB |
testcase_13 | AC | 109 ms
26,768 KB |
testcase_14 | AC | 106 ms
26,772 KB |
testcase_15 | AC | 106 ms
26,772 KB |
testcase_16 | AC | 283 ms
27,012 KB |
testcase_17 | AC | 284 ms
27,084 KB |
testcase_18 | AC | 285 ms
27,016 KB |
testcase_19 | AC | 291 ms
27,088 KB |
testcase_20 | AC | 287 ms
27,072 KB |
testcase_21 | AC | 285 ms
27,016 KB |
testcase_22 | AC | 289 ms
27,072 KB |
testcase_23 | AC | 288 ms
27,076 KB |
testcase_24 | AC | 284 ms
27,068 KB |
testcase_25 | AC | 287 ms
27,064 KB |
testcase_26 | AC | 88 ms
26,684 KB |
testcase_27 | AC | 52 ms
26,720 KB |
testcase_28 | AC | 34 ms
5,640 KB |
testcase_29 | AC | 36 ms
5,712 KB |
testcase_30 | AC | 35 ms
5,608 KB |
testcase_31 | AC | 33 ms
5,644 KB |
testcase_32 | AC | 36 ms
5,604 KB |
testcase_33 | AC | 37 ms
5,700 KB |
testcase_34 | AC | 35 ms
5,640 KB |
testcase_35 | AC | 34 ms
5,696 KB |
testcase_36 | AC | 34 ms
5,688 KB |
testcase_37 | AC | 36 ms
5,692 KB |
testcase_38 | AC | 192 ms
16,300 KB |
testcase_39 | AC | 77 ms
6,544 KB |
testcase_40 | AC | 300 ms
26,988 KB |
testcase_41 | AC | 110 ms
8,996 KB |
testcase_42 | AC | 178 ms
16,068 KB |
testcase_43 | AC | 133 ms
11,548 KB |
testcase_44 | AC | 242 ms
17,524 KB |
testcase_45 | AC | 210 ms
17,056 KB |
testcase_46 | AC | 159 ms
11,824 KB |
testcase_47 | AC | 197 ms
16,664 KB |
ソースコード
struct Scanner<R> { r: R, buf: Vec<u8> } impl<R: std::io::BufRead> Scanner<R> { fn new(r: R) -> Scanner<R> { Scanner { r, buf: Vec::with_capacity(8000) } } fn next(&mut self) -> &str { self.buf.clear(); loop { let (done, used) = { let available = self.r.fill_buf().unwrap(); match available.iter().position(|b| !b.is_ascii_whitespace()) { Some(i) => (true, i), None => (false, available.len()), } }; self.r.consume(used); if done || used == 0 { break; } } loop { let (done, used) = { let available = self.r.fill_buf().unwrap(); match available.iter().position(|b| b.is_ascii_whitespace()) { Some(i) => { self.buf.extend_from_slice(&available[..i]); (true, i) } None => { self.buf.extend_from_slice(&available); (false, available.len()) } } }; self.r.consume(used); if done || used == 0 { unsafe { return std::str::from_utf8_unchecked(&self.buf); } } } } } macro_rules! parse { ($s:expr, Chars) => ($s.chars().collect::<Vec<_>>()); ($s:expr, Bytes) => ($s.bytes().collect::<Vec<_>>()); ($s:expr, Usize1) => (parse!($s, usize) - 1); ($s:expr, $t:ty) => ($s.parse::<$t>().unwrap()); } macro_rules! read { ($sc:expr, [$t:tt; $n:expr]) => ( (0..$n).map(|_| read!($sc, $t)).collect::<Vec<_>>() ); ($sc:expr, ($($t:tt),*)) => (($(read!($sc, $t)),*)); ($sc:expr, $t:ident) => (parse!($sc.next(), $t)); ($sc:expr, $($t:tt),*) => (($(read!($sc, $t)),*)); } // reference: https://github.com/atcoder/ac-library struct SegmentTree<T> { n: usize, len: usize, height: usize, op: fn(T, T) -> T, e: fn() -> T, node: Vec<T>, } impl<T: Clone + Copy> SegmentTree<T> { fn new(n: usize, op: fn(T, T) -> T, e: fn() -> T) -> SegmentTree<T> { let (mut len, mut height) = (1, 1); while len < n { len *= 2; height += 1; } let node = vec![e(); 2 * len]; SegmentTree { n, len, height, op, e, node } } fn from(v: &[T], op: fn(T, T) -> T, e: fn() -> T) -> SegmentTree<T> { let mut st = SegmentTree::new(v.len(), op, e); for i in 0..v.len() { st.node[i + st.len] = v[i]; } for i in (1..st.len).rev() { st.update(i); } st } fn update(&mut self, k: usize) { self.node[k] = (self.op)(self.node[2 * k], self.node[2 * k + 1]); } fn set(&mut self, mut p: usize, x: T) { assert!(p < self.n); p += self.len; self.node[p] = x; for i in 1..self.height { self.update(p >> i) }; } fn prod(&self, mut l: usize, mut r: usize) -> T { assert!(l <= r && r <= self.n); let (mut sml, mut smr) = ((self.e)(), (self.e)()); l += self.len; r += self.len; while l < r { if l & 1 != 0 { sml = (self.op)(sml, self.node[l]); l += 1; } if r & 1 != 0 { r -= 1; smr = (self.op)(self.node[r], smr); } l >>= 1; r >>= 1; } (self.op)(sml, smr) } } fn main() { use std::io::Write; let (stdin, stdout) = (std::io::stdin(), std::io::stdout()); let mut scanner = Scanner::new(stdin.lock()); let mut writer = std::io::BufWriter::new(stdout.lock()); macro_rules! scan { ($($t:tt)*) => (read!(scanner, $($t)*)); } macro_rules! println { ($($arg:tt)*) => (writeln!(writer, $($arg)*).ok()); } const INF: i64 = 1 << 60; use std::cmp::{max, min}; let n = scan!(usize); let x = scan!([i64; n]); let q = scan!(usize); let queries = scan!([(Usize1, Usize1, i64); q]); let mut low_st = SegmentTree::new(n, |v1, v2| max(v1, v2), || -INF); let mut high_st = SegmentTree::from(&x, |v1, v2| min(v1, v2), || INF); let mut query_order = (0..q).collect::<Vec<_>>(); query_order.sort_by_key(|&i| queries[i].2); let mut x_order = (0..n).collect::<Vec<_>>(); x_order.sort_by_key(|&i| x[i]); let mut ans = vec![0; q]; let mut k = 0; for i in query_order { let (l, r, y) = queries[i]; while k < n && x[x_order[k]] <= y { let j = x_order[k]; low_st.set(j, x[j]); high_st.set(j, std::i64::MAX); k += 1; } ans[i] = min( y - low_st.prod(l, r + 1), high_st.prod(l, r + 1) - y, ); } for ans in ans { println!("{}", ans); } }