結果
問題 | No.1982 [Cherry 4th Tune B] 絶険 |
ユーザー | akakimidori |
提出日時 | 2022-04-04 21:22:07 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 227 ms / 3,000 ms |
コード長 | 3,063 bytes |
コンパイル時間 | 3,735 ms |
コンパイル使用メモリ | 169,600 KB |
実行使用メモリ | 46,560 KB |
最終ジャッジ日時 | 2024-04-17 12:30:06 |
合計ジャッジ時間 | 12,386 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 71 ms
15,308 KB |
testcase_04 | AC | 100 ms
22,884 KB |
testcase_05 | AC | 87 ms
18,428 KB |
testcase_06 | AC | 121 ms
25,572 KB |
testcase_07 | AC | 144 ms
28,876 KB |
testcase_08 | AC | 101 ms
22,728 KB |
testcase_09 | AC | 112 ms
24,460 KB |
testcase_10 | AC | 127 ms
26,740 KB |
testcase_11 | AC | 76 ms
16,884 KB |
testcase_12 | AC | 133 ms
26,940 KB |
testcase_13 | AC | 80 ms
15,456 KB |
testcase_14 | AC | 117 ms
26,680 KB |
testcase_15 | AC | 81 ms
15,380 KB |
testcase_16 | AC | 105 ms
24,448 KB |
testcase_17 | AC | 190 ms
32,412 KB |
testcase_18 | AC | 161 ms
30,616 KB |
testcase_19 | AC | 187 ms
34,140 KB |
testcase_20 | AC | 29 ms
7,672 KB |
testcase_21 | AC | 42 ms
10,048 KB |
testcase_22 | AC | 101 ms
23,276 KB |
testcase_23 | AC | 40 ms
8,848 KB |
testcase_24 | AC | 80 ms
17,296 KB |
testcase_25 | AC | 185 ms
33,624 KB |
testcase_26 | AC | 174 ms
31,760 KB |
testcase_27 | AC | 37 ms
9,304 KB |
testcase_28 | AC | 69 ms
15,348 KB |
testcase_29 | AC | 204 ms
46,436 KB |
testcase_30 | AC | 142 ms
46,556 KB |
testcase_31 | AC | 72 ms
15,348 KB |
testcase_32 | AC | 227 ms
46,304 KB |
testcase_33 | AC | 196 ms
46,432 KB |
testcase_34 | AC | 189 ms
46,560 KB |
ソースコード
fn main() { let (_, p, ask) = read(); #[derive(Debug, Ord, PartialOrd, Eq, PartialEq)] enum Event { Add(usize, i64), Query(usize, i64), } let mut event = vec![]; for (i, &(l, r, _, h)) in p.iter().enumerate() { event.push((l, Event::Add(i + 1, h))); event.push((r + 1, Event::Add(i + 1, -h))); } for (i, &(a, x)) in ask.iter().enumerate() { event.push((a, Event::Query(i, x))); } event.sort(); let mut bit = Fenwick::new(p.len(), 0); let mut ans = vec![-1; ask.len()]; for (_, e) in event { match e { Event::Add(x, v) => bit.add(x, v), Event::Query(k, s) => { if bit.sum(p.len()) >= s { let pos = bit.search(s); ans[k] = p[pos - 1].2; } }, } } let mut out = String::new(); for ans in ans { use std::fmt::*; writeln!(&mut out, "{}", ans).ok(); } print!("{}", out); } fn read() -> (usize, Vec<(usize, usize, i32, i64)>, Vec<(usize, i64)>) { let mut s = String::new(); use std::io::Read; std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace().flat_map(|s| s.parse::<usize>()); let mut next = || it.next().unwrap(); let n = next(); let k = next(); let q = next(); let p = (0..k) .map(|_| (next(), next(), next() as i32, next() as i64)) .collect::<Vec<_>>(); let ask = (0..q).map(|_| (next(), next() as i64)).collect::<Vec<_>>(); (n, p, ask) } // ---------- begin fenwick tree ---------- pub struct Fenwick<T> { zero: T, a: Box<[T]>, } impl<T> Fenwick<T> where T: Copy + std::ops::Add<Output = T>, { pub fn new(size: usize, zero: T) -> Fenwick<T> { Fenwick { zero: zero, a: vec![zero; size + 1].into_boxed_slice(), } } pub fn init(&mut self) { for a in self.a.iter_mut() { *a = self.zero; } } pub fn add(&mut self, mut x: usize, v: T) { assert!(x > 0); while let Some(a) = self.a.get_mut(x) { *a = *a + v; x += x & (!x + 1); } } pub fn sum(&self, mut x: usize) -> T { assert!(x < self.a.len()); let mut res = self.zero; while x > 0 { res = res + self.a[x]; x -= x & (!x + 1); } res } } impl<T> Fenwick<T> where T: Copy + std::ops::Add<Output = T> + PartialOrd, { pub fn search(&self, s: T) -> usize { debug_assert!(self.sum(self.a.len() - 1) >= s); let mut k = 1; while 2 * k < self.a.len() { k *= 2; } let mut x = 0; let mut w = self.zero; while k > 0 { self.a.get(x + k).map(|a| { if w + *a < s { w = w + *a; x += k; } }); k >>= 1; } x + 1 } } // ---------- end fenwick tree ----------