結果
問題 | No.1079 まお |
ユーザー |
![]() |
提出日時 | 2021-10-14 10:10:05 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 1,557 bytes |
コンパイル時間 | 14,609 ms |
コンパイル使用メモリ | 379,572 KB |
実行使用メモリ | 5,576 KB |
最終ジャッジ日時 | 2024-09-17 16:30:03 |
合計ジャッジ時間 | 17,077 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
fn read() -> (i32, Vec<i32>) {let mut s = String::new();use std::io::Read;std::io::stdin().read_to_string(&mut s).unwrap();let mut it = s.trim().split_whitespace().flat_map(|s| s.parse::<i32>());let mut next = || it.next().unwrap();let n = next();let k = next();(k, (0..n).map(|_| next()).collect())}fn calc(l: &[i32], r: &[i32], k: i32) -> usize {let mut map = std::collections::HashMap::new();let mut min = std::i32::MAX;let mut cnt = 0;let mut x = 0;let mut ans = 0;for (i, &r) in r.iter().enumerate() {if min > r {min = r;cnt = 1;} else if min == r {cnt += 1;}while l.get(x).map_or(false, |l| *l > min) {let po = map.entry(l[x]).or_insert((0, 0));po.0 += 1;po.1 += x + 1;x += 1;}if cnt == 1 {if let Some(po) = map.get(&(k - r)) {ans += po.0 * (i + 1) + po.1;}}}ans}fn run() {let (k, mut a) = read();let mut ans = 0;let mut dfs = vec![a.as_mut_slice()];while let Some(a) = dfs.pop() {if a.len() == 1 {if a[0] * 2 == k {ans += 1;}continue;}let m = a.len() / 2;let (l, r) = a.split_at_mut(m);l.reverse();ans += calc(l, r, k) + calc(r, l, k);dfs.push(l);dfs.push(r);}println!("{}", ans);}fn main() {run();}