use proconio::input; use std::cmp::Ordering; use std::collections::HashMap; const MIN_X: i64 = -1_000_000_000_000; const MAX_X: i64 = 1_000_000_000_000; // gcd fn calc_gcd(mut a: i64, mut b: i64) -> i64 { if a < b { std::mem::swap(&mut a, &mut b); } while b != 0 { let r = a % b; a = b; b = r; } a } // 正規化された直線方向 fn calc_(mut k: i64, mut l: i64, cache: &mut HashMap<(i64, i64), (i64, i64)>) -> (i64, i64) { if l == 0 { return (0, 1); } if let Some(&v) = cache.get(&(k, l)) { return v; } let g = calc_gcd(k.abs(), l.abs()); let key = (k, l); if k < 0 { k = -k; l = -l; } let res = (-l / g, k / g); cache.insert(key, res); res } // Fenwick Tree struct BIT { n: usize, data: Vec<(i64, i64)>, } impl BIT { fn new(n: usize) -> Self { Self { n, data: vec![(0, 0); n + 1], } } fn add(&mut self, mut i: usize, v: (i64, i64)) { while i <= self.n { self.data[i].0 += v.0; self.data[i].1 += v.1; i += i & (!i + 1); } } fn sum(&self, mut i: usize) -> (i64, i64) { let mut res = (0, 0); while i > 0 { res.0 += self.data[i].0; res.1 += self.data[i].1; i -= i & (!i + 1); } res } } fn main() { input! { q: usize, } let mut queries = Vec::new(); for _ in 0..q { input! { k: i64, l: i64, m: i64, n: i64, x: i64 } queries.push((k, l, m, n, x)); } let mut calc_cache = HashMap::new(); // 座標圧縮 let mut x_set = Vec::new(); x_set.push((MIN_X, 1)); x_set.push((MAX_X, 1)); for &(k, l, m, n, x) in &queries { x_set.push((x, 1)); if k != 0 { x_set.push(calc_(k, l, &mut calc_cache)); } if m != 0 { x_set.push(calc_(m, n, &mut calc_cache)); } } // sort (分数比較) x_set.sort_by(|a, b| { let lhs = (a.0 as i128) * (b.1 as i128); let rhs = (a.1 as i128) * (b.0 as i128); lhs.cmp(&rhs) }); x_set.dedup(); let mut x_map = HashMap::new(); for (i, &v) in x_set.iter().enumerate() { x_map.insert(v, i + 1); } let mut bit = BIT::new(x_map.len()); for &(k, l, m, n, x) in &queries { // --- 前半 --- if k == 0 { if l > 0 { bit.add(1, (0, l)); bit.add(x_map.len(), (0, -l)); } } else if k > 0 { let f1 = calc_(k, l, &mut calc_cache); bit.add(x_map[&f1], (k, l)); bit.add(x_map.len(), (-k, -l)); } else { let f1 = calc_(k, l, &mut calc_cache); bit.add(1, (k, l)); bit.add(x_map[&f1], (-k, -l)); } // --- 後半 --- if m == 0 { if n > 0 { bit.add(1, (0, -n)); bit.add(x_map.len(), (0, n)); } } else if m > 0 { let f1 = calc_(m, n, &mut calc_cache); bit.add(x_map[&f1], (-m, -n)); bit.add(x_map.len(), (m, n)); } else { let f1 = calc_(m, n, &mut calc_cache); bit.add(1, (-m, -n)); bit.add(x_map[&f1], (m, n)); } let x_idx = x_map[&(x, 1)]; let y1 = bit.sum(x_idx - 1); let y2 = bit.sum(x_idx); if y1 == (0, 0) && y2 == (0, 0) { println!("Yes"); } else { println!("No"); } } }