QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#764152 | #7711. Rikka with Lines | Jay202 | WA | 564ms | 21380kb | Rust | 4.1kb | 2024-11-20 01:27:50 | 2024-11-20 01:27:51 |
Judging History
answer
use std::io::{self, BufRead, Write};
use std::cmp::Ordering;
use std::ops::Neg;
#[derive(Debug, Clone, Copy)]
struct Rational(i128, i128);
impl Rational {
fn normalize(&self) -> Self {
let gcd = gcd(self.0, self.1);
let num = self.0 / gcd;
let den = self.1 / gcd;
if den < 0 {
Rational(-num, -den)
} else {
Rational(num, den)
}
}
}
fn gcd(a: i128, b: i128) -> i128 {
if b == 0 {
a.abs()
} else {
gcd(b, a % b)
}
}
impl Neg for Rational {
type Output = Self;
fn neg(self) -> Self::Output {
Rational(-self.0, self.1).normalize()
}
}
impl PartialEq for Rational {
fn eq(&self, other: &Self) -> bool {
let normalized_self = self.normalize();
let normalized_other = other.normalize();
normalized_self.0 == normalized_other.0 && normalized_self.1 == normalized_other.1
}
}
impl Eq for Rational {}
impl PartialOrd for Rational {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
let lhs = self.0 * other.1;
let rhs = other.0 * self.1;
lhs.partial_cmp(&rhs)
}
}
impl Ord for Rational {
fn cmp(&self, other: &Self) -> Ordering {
self.partial_cmp(other).unwrap()
}
}
struct FenwickTree {
tree: Vec<i64>,
size: usize,
}
impl FenwickTree {
pub fn new(size: usize) -> Self {
FenwickTree {
tree: vec![0; size + 1],
size,
}
}
pub fn sum(&self, idx: usize) -> i64 {
let mut sum = 0;
let mut i = idx as isize;
while i > 0 {
sum += self.tree[i as usize];
i -= i & -i;
}
sum
}
pub fn add(&mut self, idx: usize, value: i64) {
let mut i = idx as isize;
while (i as usize) <= self.size {
self.tree[i as usize] += value;
i += i & -i;
}
}
}
fn main() {
let mut iter = io::stdin().lock().lines();
let mut writer = io::BufWriter::new(io::stdout());
let t: usize = iter.next().unwrap().unwrap().trim().parse().unwrap();
for _ in 0..t {
let v: Vec<i128> = iter.next().unwrap().unwrap()
.split_whitespace().map(|x| x.parse().unwrap()).collect();
let (n, x1, y1, x2, y2) = (v[0] as usize, v[1], v[2], v[3], v[4]);
let mut seg: Vec<(usize, usize)> = vec![(0, 0); n];
let mut pos: Vec<(i32, Rational, usize, usize)> = vec![];
for i in 0..n {
let v: Vec<i128> = iter.next().unwrap().unwrap()
.split_whitespace().map(|x| x.parse().unwrap()).collect();
let (a, b) = (v[0], v[1]);
let p1 = Rational(y2 - b, a);
let mut dir = 0;
if Rational(x1, 1) < p1 && p1 <= Rational(x2, 1) {
pos.push((1, -p1, i, dir));
dir += 1;
}
let p2 = Rational(a * x1 + b, 1);
if y1 < p2.0 && p2.0 <= y2 {
pos.push((2, -p2, i, dir));
dir += 1;
}
let p3 = Rational(y1 - b, a);
if Rational(x1, 1) <= p3 && p3 < Rational(x2, 1) {
pos.push((3, p3, i, dir));
dir += 1;
}
let p4 = Rational(a * x2 + b, 1);
if y1 <= p4.0 && p4.0 < y2 {
pos.push((4, p4, i, dir));
// dir += 1;
}
}
pos.sort();
let mut idx = 1;
seg[pos[0].2].0 = idx;
seg[pos[0].2].1 = idx;
for i in 1..pos.len() {
if pos[i].0 != pos[i - 1].0 || pos[i].1 != pos[i- 1].1 { idx += 1; }
seg[pos[i].2].1 = idx;
if pos[i].3 == 0 {
seg[pos[i].2].0 = idx;
}
}
seg.sort();
let mut f = FenwickTree::new(idx);
let mut ret: i64 = 0;
for (l, r) in seg {
if l == 0 { continue; }
ret += f.sum(r) - f.sum(l - 1);
f.add(r, 1);
}
_ = writeln!(writer, "{}", ret);
}
writer.flush().unwrap();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 2100kb
input:
1 4 0 0 2 2 2 -1 1 0 -1 2 2 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: -100
Wrong Answer
time: 564ms
memory: 21380kb
input:
1000 99981 -729383395 -411431000737086146 -663099572 622842060014806018 6815159 -4872972553264521 -44664715 3425012672809037 -896158824 -386342591542384 -375531970 1040294806535662 483111943 -6742268275140254 611052273 -1055860484502308 434838119 6111752598959468 848557869 532300694586514 857250003 ...
output:
1651039 3586045792 2748851953 3152026773 39346685 75120 224 52186 548 86457 1142 70186 71755 38 112 659 104842 77057 81144 1569 1261 69699 71052 206 55 634 85880 85359 2825 1145 98613 77521 244 102670 11387 103948 65377 64348 78604 111 139 84326 86928 75648 67463 39675 115 106459 62984 396 103370 71...
result:
wrong answer 1st numbers differ - expected: '1698824', found: '1651039'