Submission #1026294
Source Code Expand
#[allow(unused_imports)] use std::cmp::*; #[allow(unused_imports)] use std::collections::*; use std::io::*; #[allow(dead_code)] fn getline() -> String { let mut ret = String::new(); std::io::stdin().read_line(&mut ret).ok(); return ret; } fn get_word() -> String { let mut stdin = std::io::stdin(); let mut u8b: [u8; 1] = [0]; loop { let mut buf: Vec<u8> = Vec::with_capacity(16); loop { let res = stdin.read(&mut u8b); if res.is_err() || res.ok().unwrap() == 0 || u8b[0] <= ' ' as u8 { break; } else { buf.push(u8b[0]); } } if buf.len() >= 1 { let ret = std::string::String::from_utf8(buf).unwrap(); return ret; } } } fn parse<T: std::str::FromStr>(s: &str) -> T { s.parse::<T>().ok().unwrap() } #[allow(dead_code)] fn get<T: std::str::FromStr>() -> T { parse(&get_word()) } /** * Sparse Table. * BiOp should be the type of a binary operator which is * associative, commutative and idempotent. * (For example, both min and gcd satisfy these properties.) */ struct SparseTable<T, BiOp> { biop: BiOp, st: Vec<Vec<T>>, } impl<T, BiOp> SparseTable<T, BiOp> where BiOp: Fn(T, T) -> T, T: Copy { pub fn new(ary: &[T], biop: BiOp) -> Self { let n = ary.len(); let mut h = 1; while 1 << h < n { h += 1; } let mut st: Vec<Vec<T>> = vec![Vec::from(ary); h + 1]; for i in 0 .. n { st[0][i] = ary[i]; } for b in 1 .. (h + 1) { if n + 1 < 1 << b { break; } for i in 0 .. (n + 1 - (1 << b)) { let next_idx = (1 << (b - 1)) + i; st[b][i] = biop(st[b - 1][i], st[b - 1][next_idx]); } } SparseTable {biop: biop, st: st} } fn top_bit(t: usize) -> usize { let mut h = 0; while 1 << h <= t { h += 1; } h - 1 } pub fn query(&self, f: usize, s: usize) -> T { assert!(f <= s); let b = Self::top_bit(s + 1 - f); let endpoint = s + 1 - (1 << b); (self.biop)(self.st[b][f], self.st[b][endpoint]) } } fn sol_spt(n: usize, a: &[i64], s: &[char]) -> Option<i64> { let mut idx = 0; for i in 0 .. (n - 1) { if s[i] == 'm' { idx = i; break; } } for i in 0 .. idx { if s[i] != 'M' { return None; } } for i in idx .. (n - 1) { if s[i] != 'm' { return None; } } let spt: SparseTable<i64, _> = SparseTable::new(&a, |x, y| max(x, y)); let mut b: Vec<i64> = vec![0; n - idx]; for i in 0 .. (n - idx) { b[i] = spt.query(i, i + idx); } let spt2: SparseTable<i64, _> = SparseTable::new(&b, |x, y| min(x, y)); return Some(spt2.query(0, n - idx - 1)); } fn main() { let n: usize = get(); let a: Vec<i64> = (0 .. n).map(|_| get()).collect(); let s: String = get_word(); let sc: Vec<char> = s.chars().collect(); let res1 = sol_spt(n, &a, &sc); println!("{}", res1.unwrap()); }
Submission Info
Submission Time | |
---|---|
Task | B - Compression |
User | kobae964 |
Language | Rust (1.15.1) |
Score | 400 |
Code Size | 3217 Byte |
Status | RE |
Exec Time | 76 ms |
Memory | 29564 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | 0 / 800 | 0 / 200 | ||||||||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt |
subtask1 | sample_2.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 | sample_1.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt |
All | sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, 2_1.txt, 2_2.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_10.txt, subtask_3_11.txt, subtask_3_12.txt, subtask_3_13.txt, subtask_3_14.txt, subtask_3_15.txt, subtask_3_16.txt, subtask_3_17.txt, subtask_3_18.txt, subtask_3_19.txt, subtask_3_2.txt, subtask_3_20.txt, subtask_3_21.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
2_1.txt | RE | 3 ms | 380 KB |
2_2.txt | AC | 3 ms | 380 KB |
sample_1.txt | RE | 3 ms | 380 KB |
sample_2.txt | AC | 3 ms | 380 KB |
sample_3.txt | RE | 3 ms | 380 KB |
sample_4.txt | RE | 3 ms | 380 KB |
subtask_1.2_1.txt | AC | 3 ms | 380 KB |
subtask_1.2_2.txt | AC | 3 ms | 380 KB |
subtask_1_1.txt | AC | 76 ms | 29564 KB |
subtask_1_10.txt | AC | 66 ms | 22780 KB |
subtask_1_2.txt | AC | 62 ms | 18044 KB |
subtask_1_3.txt | AC | 56 ms | 16124 KB |
subtask_1_4.txt | AC | 56 ms | 17788 KB |
subtask_1_5.txt | AC | 11 ms | 3836 KB |
subtask_1_6.txt | AC | 71 ms | 26364 KB |
subtask_1_7.txt | AC | 3 ms | 380 KB |
subtask_1_8.txt | AC | 67 ms | 23676 KB |
subtask_1_9.txt | AC | 69 ms | 22908 KB |
subtask_2_1.txt | RE | 36 ms | 1660 KB |
subtask_2_10.txt | RE | 36 ms | 1660 KB |
subtask_2_2.txt | RE | 36 ms | 1660 KB |
subtask_2_3.txt | RE | 36 ms | 1660 KB |
subtask_2_4.txt | RE | 36 ms | 1660 KB |
subtask_2_5.txt | RE | 3 ms | 380 KB |
subtask_2_6.txt | AC | 3 ms | 380 KB |
subtask_2_7.txt | RE | 3 ms | 380 KB |
subtask_2_8.txt | RE | 36 ms | 1660 KB |
subtask_2_9.txt | RE | 10 ms | 764 KB |
subtask_3_1.txt | RE | 36 ms | 1660 KB |
subtask_3_10.txt | RE | 36 ms | 1660 KB |
subtask_3_11.txt | RE | 36 ms | 1660 KB |
subtask_3_12.txt | RE | 46 ms | 1660 KB |
subtask_3_13.txt | RE | 36 ms | 1660 KB |
subtask_3_14.txt | RE | 36 ms | 1660 KB |
subtask_3_15.txt | RE | 36 ms | 1660 KB |
subtask_3_16.txt | RE | 36 ms | 1660 KB |
subtask_3_17.txt | RE | 37 ms | 1660 KB |
subtask_3_18.txt | RE | 36 ms | 1660 KB |
subtask_3_19.txt | RE | 37 ms | 1660 KB |
subtask_3_2.txt | RE | 36 ms | 1660 KB |
subtask_3_20.txt | RE | 37 ms | 1660 KB |
subtask_3_21.txt | RE | 36 ms | 1660 KB |
subtask_3_3.txt | RE | 6 ms | 636 KB |
subtask_3_4.txt | RE | 33 ms | 1532 KB |
subtask_3_5.txt | RE | 30 ms | 1404 KB |
subtask_3_6.txt | RE | 37 ms | 1660 KB |
subtask_3_7.txt | RE | 37 ms | 1788 KB |
subtask_3_8.txt | RE | 37 ms | 1660 KB |
subtask_3_9.txt | RE | 36 ms | 1660 KB |