Submission #68181071

---

Source Code Expand

use proconio::{fastout, input};
use std::{collections::BTreeMap, mem::swap};

#[fastout]
pub fn main() {
    input!(n: usize, pab: [(usize, usize, usize); n], q: usize, x: [usize; q]);
    let mut map = BTreeMap::<usize, Vec<usize>>::new();
    for i in 0..q {
        map.entry(x[i]).or_default().push(i);
    }
    let mut acc = 0;
    let mut stack = vec![];
    for (p, a, b) in pab {
        while let Some((&key, _)) = map.range(..=p + acc).next() {
            let value = map.remove(&key).unwrap();
            stack.push((key.saturating_sub(acc) + acc + a + b, value));
        }
        while let Some((key, mut value)) = stack.pop() {
            map.entry(key)
                .and_modify(|e| {
                    if e.len() < value.len() {
                        swap(e, &mut value);
                    }
                    e.extend(&value);
                })
                .or_insert_with(|| value);
        }
        acc += b;
    }
    let mut ans = vec![0; q];
    for (key, value) in map {
        for i in value {
            ans[i] = key.saturating_sub(acc);
        }
    }
    for ans in ans {
        println!("{ans}");
    }
}

Submission Info

Judge Result