結果
問題 | No.1435 Mmm...... |
ユーザー | fukafukatani |
提出日時 | 2021-04-04 10:41:54 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 742 ms / 2,000 ms |
コード長 | 4,585 bytes |
コンパイル時間 | 4,032 ms |
コンパイル使用メモリ | 165,408 KB |
実行使用メモリ | 14,384 KB |
最終ジャッジ日時 | 2023-08-27 06:19:22 |
合計ジャッジ時間 | 15,938 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 446 ms
10,704 KB |
testcase_07 | AC | 551 ms
11,560 KB |
testcase_08 | AC | 640 ms
12,580 KB |
testcase_09 | AC | 599 ms
12,352 KB |
testcase_10 | AC | 503 ms
10,928 KB |
testcase_11 | AC | 495 ms
10,792 KB |
testcase_12 | AC | 459 ms
10,516 KB |
testcase_13 | AC | 445 ms
9,976 KB |
testcase_14 | AC | 316 ms
7,652 KB |
testcase_15 | AC | 673 ms
12,988 KB |
testcase_16 | AC | 547 ms
11,536 KB |
testcase_17 | AC | 362 ms
8,424 KB |
testcase_18 | AC | 681 ms
13,244 KB |
testcase_19 | AC | 483 ms
11,244 KB |
testcase_20 | AC | 615 ms
12,348 KB |
testcase_21 | AC | 254 ms
14,384 KB |
testcase_22 | AC | 598 ms
14,032 KB |
testcase_23 | AC | 717 ms
13,152 KB |
testcase_24 | AC | 708 ms
13,544 KB |
testcase_25 | AC | 720 ms
13,248 KB |
testcase_26 | AC | 742 ms
13,476 KB |
testcase_27 | AC | 718 ms
13,300 KB |
コンパイルメッセージ
warning: value assigned to `l` is never read --> Main.rs:52:21 | 52 | let mut l = 0; | ^ | = help: maybe it is overwritten before being read? = note: `#[warn(unused_assignments)]` on by default warning: 1 warning emitted
ソースコード
#![allow(unused_imports)] use std::cmp::*; use std::collections::*; use std::io::Write; use std::ops::Bound::*; #[allow(unused_macros)] macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; } fn main() { let n = read::<usize>(); let mut ans = 0i64; let mut a = read_vec::<i64>(); for ti in 0..2 { let mut aa = a .iter() .enumerate() .map(|(i, &x)| (x, i)) .collect::<Vec<_>>(); if ti == 0 { aa.sort_by_key(|&(x, i)| (x, Reverse(i))); } else { aa.sort(); } let mut seg = SegTree::new(n, 0i64, max); for i in 0..n { seg.update(i, a[i]); } let mut poses = BTreeSet::new(); for (m2, i) in aa { poses.insert(i); let r_iter = poses.range((Unbounded, Excluded(i))); let r; if let Some(x) = r_iter.rev().next() { r = x + 1; } else { r = 0; } let mut l_iter = poses.range((Excluded(i), Unbounded)); let mut l = 0; if let Some(x) = l_iter.next() { l = *x; } else { continue; } let m1 = a[l]; let ll; if let Some(x) = l_iter.next() { ll = x - 1; } else { ll = n - 1; } // debug!((m2, r, l, ll)); let m = seg.query(i, l + 1); if m > m1 + m2 { continue; } let lld; if seg.query(i, ll + 1) <= m1 + m2 { lld = ll; } else { let (ok, _) = binary_search(i, ll, |mid| seg.query(i, mid + 1) <= m1 + m2); lld = ok; } let rd; if seg.query(r, i + 1) <= m1 + m2 { rd = r; } else { let (_, ok) = binary_search(r, i, |mid| seg.query(mid, i + 1) > m1 + m2); rd = ok; } let temp = (lld - l + 1) as i64 * (i - rd + 1) as i64; // debug!((i, lld, rd, temp)); ans += temp; } a.reverse(); } println!("{}", ans); } type Input = usize; fn binary_search<F>(lb: Input, ub: Input, criterion: F) -> (Input, Input) where F: Fn(Input) -> bool, { assert_eq!(criterion(lb), true); assert_eq!(criterion(ub), false); let mut ok = lb; let mut ng = ub; while ng - ok > 1 { let mid = (ng + ok) / 2; if criterion(mid) { ok = mid; } else { ng = mid; } } (ok, ng) } fn read<T: std::str::FromStr>() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[derive(Clone)] struct SegTree<T, F> where F: Fn(T, T) -> T, T: std::clone::Clone + std::marker::Copy, { n: usize, dat: Vec<T>, init: T, functor: F, } impl<T, F> SegTree<T, F> where F: Fn(T, T) -> T, T: std::clone::Clone + std::marker::Copy, { fn new(n: usize, init: T, f: F) -> SegTree<T, F> { let mut m = 1; // For simplicity, we use 2 ** n sized SegTree. while m < n { m *= 2; } SegTree { n: m, dat: vec![init; 2 * m - 1], init: init, functor: f, } } // dat[k] = a; fn update(&mut self, k: usize, a: T) { let mut k = k; k += self.n - 1; self.dat[k] = a; while k > 0 { k = (k - 1) / 2; self.dat[k] = (self.functor)(self.dat[k * 2 + 1], self.dat[k * 2 + 2]); } } // [a, b) fn query(&self, a: usize, b: usize) -> T { self.query_inner(a, b, 0, 0, self.n) } fn query_inner(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> T { if r <= a || b <= l { return self.init; } if a <= l && r <= b { return self.dat[k]; } let vl = self.query_inner(a, b, k * 2 + 1, l, (l + r) / 2); let vr = self.query_inner(a, b, k * 2 + 2, (l + r) / 2, r); (self.functor)(vl, vr) } }