結果
問題 | No.992 最長増加部分列の数え上げ |
ユーザー |
![]() |
提出日時 | 2020-02-14 23:35:56 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 91 ms / 2,000 ms |
コード長 | 1,491 bytes |
コンパイル時間 | 14,648 ms |
コンパイル使用メモリ | 385,992 KB |
実行使用メモリ | 9,440 KB |
最終ジャッジ日時 | 2024-10-06 13:29:03 |
合計ジャッジ時間 | 19,381 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
use std::io::Read;use std::cmp::Ordering;use std::ops::*;const MOD: u32 = 1_000_000_007;#[derive(Clone, Copy)]struct MaxCnt(usize, u32);impl Add for MaxCnt {type Output = Self;fn add(self, rhs: Self) -> Self::Output {match self.0.cmp(&rhs.0) {Ordering::Less => rhs,Ordering::Greater => self,Ordering::Equal => MaxCnt(self.0, (self.1 + rhs.1) % MOD),}}}fn add(bit: &mut [MaxCnt], x: usize, v: MaxCnt) {let mut i = x;while i < bit.len() {bit[i] = bit[i] + v;i += i & (!i + 1);}}fn sum(bit: &[MaxCnt], x: usize) -> MaxCnt {let mut ans = MaxCnt(0, 1);let mut i = x;while i > 0 {ans = ans + bit[i];i -= i & (!i + 1);}ans}fn run() {let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();let mut it = s.trim().split_whitespace();let n: usize = it.next().unwrap().parse().unwrap();let a: Vec<i32> = it.map(|s| s.parse().unwrap()).collect();assert!(a.len() == n);let mut b = a.clone();b.push(-1_000_000_000 - 1);b.sort();b.dedup();let a: Vec<usize> = a.into_iter().map(|a| b.binary_search(&a).unwrap()).collect();let mut bit = vec![MaxCnt(0, 0); b.len()];for a in a {let s = sum(&bit, a - 1);add(&mut bit, a, MaxCnt(s.0 + 1, s.1));}let ans = sum(&bit, b.len() - 1).1;println!("{}", ans);}fn main() {run();}