結果
| 問題 | No.2500 Products in a Range |
| ユーザー |
 naut3
|
| 提出日時 | 2023-10-13 21:40:42 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,319 bytes |
| コンパイル時間 | 14,236 ms |
| コンパイル使用メモリ | 379,272 KB |
| 実行使用メモリ | 10,752 KB |
| 最終ジャッジ日時 | 2024-09-15 17:18:18 |
| 合計ジャッジ時間 | 18,706 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
10,752 KB |
| testcase_01 | AC | 1 ms
5,248 KB |
| testcase_02 | AC | 20 ms
5,376 KB |
| testcase_03 | AC | 12 ms
5,376 KB |
| testcase_04 | AC | 29 ms
5,376 KB |
| testcase_05 | AC | 25 ms
5,376 KB |
| testcase_06 | AC | 2 ms
5,376 KB |
| testcase_07 | AC | 467 ms
5,376 KB |
| testcase_08 | TLE | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
ソースコード
#![allow(non_snake_case, unused_imports, unused_must_use)]
use std::io::{self, prelude::*};
use std::str;
fn main() {
let (stdin, stdout) = (io::stdin(), io::stdout());
let mut scan = Scanner::new(stdin.lock());
let mut out = io::BufWriter::new(stdout.lock());
macro_rules! input {
($T: ty) => {
scan.token::<$T>()
};
($T: ty, $N: expr) => {
(0..$N).map(|_| scan.token::<$T>()).collect::<Vec<_>>()
};
}
let N = input!(usize);
let L = input!(isize);
let R = input!(isize);
let mut A = input!(isize, N);
A.sort();
let A = A;
let mut ans = 1;
for l in 0..N {
let mut neg: std::collections::BTreeSet<(isize, usize)> = std::collections::BTreeSet::new();
let mut zer: std::collections::BTreeSet<(isize, usize)> = std::collections::BTreeSet::new();
let mut pos: std::collections::BTreeSet<(isize, usize)> = std::collections::BTreeSet::new();
let a = A[l];
if a < 0 {
neg.insert((a, l));
} else if a == 0 {
zer.insert((a, l));
} else {
pos.insert((a, l));
}
if l + 1 < N {
let a = A[l + 1];
if a < 0 {
neg.insert((a, l + 1));
} else if a == 0 {
zer.insert((a, l + 1));
} else {
pos.insert((a, l + 1));
}
}
for r in l + 2..=N {
if r - l > ans {
// [l, r) は ok か?
let mut cand = std::collections::BTreeSet::new();
let n1 = neg.range(..).next();
match n1 {
Some(&(v, i)) => {
cand.insert((v, i));
let n2 = neg.range((v, i + 1)..).next();
match n2 {
Some(&(v2, i2)) => {
cand.insert((v2, i2));
}
None => {}
}
}
None => {}
}
let nn1 = neg.range(..).next_back();
match nn1 {
Some(&(v, i)) => {
cand.insert((v, i));
let n2 = neg.range(..(v, i)).next_back();
match n2 {
Some(&(v2, i2)) => {
cand.insert((v2, i2));
}
None => {}
}
}
None => {}
}
let z1 = zer.range(..).next();
match z1 {
Some(&(v, i)) => {
cand.insert((v, i));
let n2 = zer.range((v, i + 1)..).next();
match n2 {
Some(&(v2, i2)) => {
cand.insert((v2, i2));
}
None => {}
}
}
None => {}
}
let p1 = pos.range(..).next();
match p1 {
Some(&(v, i)) => {
cand.insert((v, i));
let n2 = pos.range((v, i + 1)..).next();
match n2 {
Some(&(v2, i2)) => {
cand.insert((v2, i2));
}
None => {}
}
}
None => {}
}
let pp1 = pos.range(..).next_back();
match pp1 {
Some(&(v, i)) => {
cand.insert((v, i));
let n2 = pos.range(..(v, i)).next_back();
match n2 {
Some(&(v2, i2)) => {
cand.insert((v2, i2));
}
None => {}
}
}
None => {}
}
let C = cand.iter().map(|&(k, _)| k).collect::<Vec<_>>();
let mut D = vec![];
let length = C.len();
for i in 0..length {
for j in i + 1..length {
D.push(C[i] * C[j]);
}
}
// eprintln!(
// "{}",
// C.iter()
// .map(|x| x.to_string())
// .collect::<Vec<_>>()
// .join(" ")
// );
D.sort();
let l2 = D.len();
let m = D[0];
let M = D[l2 - 1];
if L <= m && R >= M {
ans = std::cmp::max(ans, r - l);
}
}
// A[r]を追加する.
if r != N {
let a = A[r];
if a < 0 {
neg.insert((a, r));
} else if a == 0 {
zer.insert((a, r));
} else {
pos.insert((a, r));
}
}
}
}
writeln!(out, "{}", ans);
}
struct Scanner<R> {
reader: R,
buf_str: Vec<u8>,
buf_iter: str::SplitWhitespace<'static>,
}
impl<R: BufRead> Scanner<R> {
fn new(reader: R) -> Self {
Self {
reader,
buf_str: vec![],
buf_iter: "".split_whitespace(),
}
}
fn token<T: str::FromStr>(&mut self) -> T {
loop {
if let Some(token) = self.buf_iter.next() {
return token.parse().ok().expect("Failed parse");
}
self.buf_str.clear();
self.reader
.read_until(b'\n', &mut self.buf_str)
.expect("Failed read");
self.buf_iter = unsafe {
let slice = str::from_utf8_unchecked(&self.buf_str);
std::mem::transmute(slice.split_whitespace())
}
}
}
}