結果
問題 | No.1675 Strange Minimum Query |
ユーザー | akakimidori |
提出日時 | 2021-08-14 01:08:36 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 130 ms / 2,000 ms |
コード長 | 4,467 bytes |
コンパイル時間 | 2,465 ms |
コンパイル使用メモリ | 169,784 KB |
実行使用メモリ | 30,052 KB |
最終ジャッジ日時 | 2023-09-02 15:07:25 |
合計ジャッジ時間 | 9,333 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 45 ms
11,928 KB |
testcase_04 | AC | 44 ms
11,772 KB |
testcase_05 | AC | 15 ms
5,284 KB |
testcase_06 | AC | 52 ms
12,508 KB |
testcase_07 | AC | 59 ms
17,016 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 77 ms
17,808 KB |
testcase_11 | AC | 35 ms
13,848 KB |
testcase_12 | AC | 87 ms
19,440 KB |
testcase_13 | AC | 77 ms
26,680 KB |
testcase_14 | AC | 109 ms
30,052 KB |
testcase_15 | AC | 97 ms
26,248 KB |
testcase_16 | AC | 1 ms
4,380 KB |
testcase_17 | AC | 24 ms
7,052 KB |
testcase_18 | AC | 31 ms
8,304 KB |
testcase_19 | AC | 58 ms
17,628 KB |
testcase_20 | AC | 87 ms
20,300 KB |
testcase_21 | AC | 86 ms
20,656 KB |
testcase_22 | AC | 104 ms
24,204 KB |
testcase_23 | AC | 69 ms
14,000 KB |
testcase_24 | AC | 72 ms
15,320 KB |
testcase_25 | AC | 49 ms
10,392 KB |
testcase_26 | AC | 35 ms
10,252 KB |
testcase_27 | AC | 82 ms
21,012 KB |
testcase_28 | AC | 50 ms
15,128 KB |
testcase_29 | AC | 48 ms
16,340 KB |
testcase_30 | AC | 35 ms
10,744 KB |
testcase_31 | AC | 88 ms
16,132 KB |
testcase_32 | AC | 129 ms
26,100 KB |
testcase_33 | AC | 125 ms
25,920 KB |
testcase_34 | AC | 128 ms
26,024 KB |
testcase_35 | AC | 130 ms
26,104 KB |
testcase_36 | AC | 129 ms
26,048 KB |
ソースコード
// ---------- begin SegmentTree Point update Range query ---------- mod segment_tree { pub struct PURQ<T, F> { size: usize, data: Vec<T>, e: T, op: F, } #[allow(dead_code)] impl<T, F> PURQ<T, F> where T: Clone, F: Fn(&T, &T) -> T, { pub fn new(size: usize, e: T, op: F) -> PURQ<T, F> { let size = size.next_power_of_two(); PURQ { size, data: vec![e.clone(); 2 * size], e: e, op: op, } } pub fn update(&mut self, x: usize, v: T) { assert!(x < self.size); let mut x = x + self.size; let data = &mut self.data; data[x] = v; x >>= 1; while x > 0 { data[x] = (self.op)(&data[2 * x], &data[2 * x + 1]); x >>= 1; } } pub fn update_tmp(&mut self, x: usize, v: T) { assert!(x < self.size); self.data[x + self.size] = v; } pub fn update_all(&mut self) { let data = &mut self.data; for k in (1..self.size).rev() { data[k] = (self.op)(&data[2 * k], &data[2 * k + 1]); } } pub fn find(&self, l: usize, r: usize) -> T { assert!(l <= r && r <= self.size); if l == r { return self.e.clone(); } let mut p = self.e.clone(); let mut q = self.e.clone(); let mut l = l + self.size; let mut r = r + self.size; let data = &self.data; while l < r { if l & 1 == 1 { p = (self.op)(&p, &data[l]); l += 1; } if r & 1 == 1 { r -= 1; q = (self.op)(&data[r], &q); } l >>= 1; r >>= 1; } (self.op)(&p, &q) } } } // ---------- end SegmentTree Point update Range query ---------- // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::<Vec<char>>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::<Vec<u8>>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- use std::collections::*; type Set<T> = BTreeSet<T>; fn run() { input! { n: usize, q: usize, ask: [(usize1, usize, u32); q], } let mut ask = ask; ask.sort_by_key(|p| p.2); let mut set = (0..n).collect::<Set<_>>(); let mut ans = vec![1; n]; for &(l, r, v) in ask.iter().rev() { let x = set.range(l..r).cloned().collect::<Vec<_>>(); for x in x { ans[x] = v; set.remove(&x); } } let mut seg = segment_tree::PURQ::new(n, std::u32::MAX, |a, b| std::cmp::min(*a, *b)); for (i, v) in ans.iter().enumerate() { seg.update_tmp(i, *v); } seg.update_all(); for &(l, r, v) in ask.iter() { if seg.find(l, r) != v { println!("-1"); return; } } let s = ans.iter().map(|a| a.to_string()).collect::<Vec<_>>().join(" "); println!("{}", s); } fn main() { run(); }