結果
問題 | No.2735 Demarcation |
ユーザー |
![]() |
提出日時 | 2024-04-19 23:18:39 |
言語 | Rust (1.83.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 |
コンパイルメッセージ
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);}}