#1152816 (Rust) No.2974 関数の芽

• 問題: No.2974 関数の芽
• ユーザー: LyricalMaestro
• 提出日時: 2026-03-19 02:19:40
• 言語: Rust (1.93.0 + proconio + num + itertools)
• 結果: RE
• 実行時間: -
• コード長: 3,592 bytes
• コンパイル時間: 13,121 ms
• コンパイル使用メモリ: 204,032 KB
• 実行使用メモリ: 27,720 KB
• 最終ジャッジ日時: 2026-03-19 02:19:57
• 合計ジャッジ時間: 15,528 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_1

ファイルパターン	結果
other	AC * 22 RE * 2

コンパイルメッセージ

warning: unused import: `std::cmp::Ordering`
 --> src/main.rs:2:5
  |
2 | use std::cmp::Ordering;
  |     ^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` (part of `#[warn(unused)]`) on by default

ソースコード

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());

    if k < 0 {
        k = -k;
        l = -l;
    }

    let res = (-l / g, k / g);
    cache.insert((k, l), 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 * b.1;
        let rhs = a.1 * b.0;
        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");
        }
    }
}