結果
問題 | No.2735 Demarcation |
ユーザー | yosupot |
提出日時 | 2024-04-19 23:18:39 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 128 ms / 1,500 ms |
コード長 | 2,427 bytes |
コンパイル時間 | 17,621 ms |
コンパイル使用メモリ | 401,220 KB |
実行使用メモリ | 20,800 KB |
最終ジャッジ日時 | 2024-10-11 17:49:26 |
合計ジャッジ時間 | 21,535 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | AC | 33 ms
11,656 KB |
testcase_05 | AC | 21 ms
5,248 KB |
testcase_06 | AC | 57 ms
16,768 KB |
testcase_07 | AC | 118 ms
19,456 KB |
testcase_08 | AC | 90 ms
15,488 KB |
testcase_09 | AC | 43 ms
8,704 KB |
testcase_10 | AC | 54 ms
11,264 KB |
testcase_11 | AC | 14 ms
5,632 KB |
testcase_12 | AC | 19 ms
5,248 KB |
testcase_13 | AC | 45 ms
5,248 KB |
testcase_14 | AC | 103 ms
14,972 KB |
testcase_15 | AC | 46 ms
5,248 KB |
testcase_16 | AC | 63 ms
16,804 KB |
testcase_17 | AC | 78 ms
9,088 KB |
testcase_18 | AC | 34 ms
5,248 KB |
testcase_19 | AC | 92 ms
19,200 KB |
testcase_20 | AC | 114 ms
18,304 KB |
testcase_21 | AC | 37 ms
11,136 KB |
testcase_22 | AC | 49 ms
15,944 KB |
testcase_23 | AC | 29 ms
7,168 KB |
testcase_24 | AC | 59 ms
10,880 KB |
testcase_25 | AC | 81 ms
16,384 KB |
testcase_26 | AC | 42 ms
12,672 KB |
testcase_27 | AC | 45 ms
11,136 KB |
testcase_28 | AC | 128 ms
20,800 KB |
testcase_29 | AC | 70 ms
17,084 KB |
コンパイルメッセージ
warning: unused import: `max` --> src/main.rs:1:17 | 1 | use core::cmp::{max, min}; | ^^^ | = note: `#[warn(unused_imports)]` on by default warning: unnecessary parentheses around function argument --> src/main.rs:43:47 | 43 | let mut dp_sum = vec![0i128; min(300, (dist + 1 + 1)) as usize]; | ^ ^ | = note: `#[warn(unused_parens)]` on by default help: remove these parentheses | 43 - let mut dp_sum = vec![0i128; min(300, (dist + 1 + 1)) as usize]; 43 + let mut dp_sum = vec![0i128; min(300, dist + 1 + 1) as usize]; |
ソースコード
use core::cmp::{max, min}; use proconio::input; fn main() { input! { n: i32, x: [i32; n], q: i32, ques: [(i32, i32, i64); q], } let mut count_same = vec![0; n as usize]; for i in 0..(n - 1) { count_same[(i + 1) as usize] = count_same[i as usize] + if x[i as usize] == x[(i + 1) as usize] { 1 } else { 0 } } const MAX_K: i32 = 70; let mut freq = vec![0; (n + 1) as usize]; for (l, r, s) in ques { let l = l - 1; let dist = r - l; if dist <= 62 && 1i64 << (dist - 1) <= s { println!("-1"); continue; } let same = count_same[(r - 1) as usize] - count_same[l as usize]; if 61 <= same || s < (1i64 << same) { println!("0"); continue; } let mut dp_sum = vec![0i128; min(300, (dist + 1 + 1)) as usize]; let mut lw = 1; let mut up = MAX_K; while up - lw > 1 { let k = (lw + up) / 2; dp_sum[0] = 0; dp_sum[1] = 1; let mut left = l; let mut vis_count = 0; let mut over = false; for i in l..r { if freq[x[i as usize] as usize] == 0 { vis_count += 1; } freq[x[i as usize] as usize] += 1; while vis_count == k + 1 { freq[x[left as usize] as usize] -= 1; if freq[x[left as usize] as usize] == 0 { vis_count -= 1; } left += 1; } let dp = dp_sum[(i + 1 - l) as usize] - dp_sum[(left - l) as usize]; if dp > s as i128 { for j in l..i + 1 { freq[x[j as usize] as usize] = 0; } over = true; break; } dp_sum[(i + 1 - l + 1) as usize] = dp_sum[(i + 1 - l) as usize] + dp; } if !over { for i in l..r { freq[x[i as usize] as usize] = 0; } lw = k; } else { up = k; } } println!("{}", lw); } }