macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); let mut next = || { iter.next().unwrap() }; input_inner!{next, $($r)*} }; ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes .by_ref() .map(|r|r.unwrap() as char) .skip_while(|c|c.is_whitespace()) .take_while(|c|!c.is_whitespace()) .collect() }; input_inner!{next, $($r)*} }; } macro_rules! input_inner { ($next:expr) => {}; ($next:expr, ) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} }; } macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ( $(read_value!($next, $t)),* ) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::>() }; ($next:expr, usize1) => { read_value!($next, usize) - 1 }; ($next:expr, $t:ty) => { $next().parse::<$t>().expect("Parse error") }; } use std::cmp::max; struct SegmentTree { size: usize, values: Vec, e: I, } impl SegmentTree where I: Copy + Ord, { pub fn new(size: usize, e: I) -> Self { let mut node_size = 1; while node_size < size { node_size *= 2; } SegmentTree { size: node_size, values: vec![e; 2 * node_size - 1], e: e, } } pub fn update(&mut self, target: usize, value: I) { let mut k = target + self.size - 1; self.values[k] = value; while k > 0 { k = (k - 1) / 2; self.values[k] = max(self.values[2 * k + 1], self.values[2 * k + 2]); } } pub fn query(&self, a: usize, b: usize) -> I { self._query(a, b, 0, 0, self.size) } fn _query(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> I { if r <= a || b <= l { return self.e; } if a <= l && r <= b { return self.values[k]; } let vl = self._query(a, b, (k << 1) + 1, l, (l + r) >> 1); let vr = self._query(a, b, (k << 1) + 2, (l + r) >> 1, r); max(vl, vr) } } fn main() { input!{ n:usize, points: [(usize, usize, usize); n], } const V_MAX: usize = 10000; let mut partition_by_r = vec![]; for _ in 0..V_MAX + 1 { partition_by_r.push(vec![]); } let mut pt_max = SegmentTree::new(V_MAX + 1, 0); let mut res = vec![]; for (i, point) in points.iter().enumerate() { let (p, t, r) = *point; partition_by_r[r].push((p, t+1, i + 1)); } for ptis in partition_by_r.iter_mut().rev() { ptis.sort_unstable_by(|a, b| b.cmp(a)); for pti in ptis { let (p, t, i) = *pti; if t > pt_max.query(p, V_MAX + 1) { res.push(i); pt_max.update(p, t); } } } res.sort_unstable(); for point_id in res { println!("{}", point_id); } }