Submission #1574894
Source Code Expand
#![allow(unused_imports, unused_variables, dead_code)] use std::io::*; use std::fmt::*; use std::str::*; use std::cmp::*; use std::collections::*; pub trait InputValue { fn parse(s: &str) -> Self; } pub fn read<T: InputValue>() -> T { let mut buf = String::new(); let _ = stdin().read_line(&mut buf); T::parse(&buf.trim()) } pub fn readnc<T: InputValue>() -> Vec<T> { let mut vec = vec![]; let line: String = read(); for token in line.split_whitespace() { vec.push(T::parse(token)); } vec } pub fn readn<T: InputValue>(n: usize) -> Vec<T> { let mut vec = vec![]; for _ in 0..n { vec.push(read()); } vec } macro_rules! parse_single_value { ($($t:ty),*) => { $( impl InputValue for $t { fn parse(s: &str) -> $t { s.parse().unwrap() } } )* } } parse_single_value!(i32, i64, f32, f64, usize, String); macro_rules! parse_tuple { ($($t:ident),*) => { impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* { fn parse(s: &str) -> ($($t),*) { let mut tokens = s.split_whitespace(); let t = ($($t::parse(tokens.next().unwrap())),*); t } } } } parse_tuple!(A, B); parse_tuple!(A, B, C); // === struct Query { time: i32, initial: i32 } fn main() { let x: i32 = read(); let k: usize = read(); let mut reverse_at: Vec<i32> = readnc(); reverse_at.insert(0, 0); reverse_at.push(1000000010); let q: usize = read(); let queries: Vec<(i32, i32)> = readn(q); let queries: Vec<Query> = queries.into_iter().map(|(a, b)| { Query { time: a, initial: b } }).collect(); let mut min_sand = 0; let mut max_sand = x; let mut argmin = 0; let mut argmax = x; let mut answers: Vec<i32> = vec![0; q]; let mut head: usize = 0; let mut incr = -1; for ti in 1..k+2 { let next_reverse = reverse_at[ti]; let prev_reverse = reverse_at[ti-1]; while head < q && queries[head].time < next_reverse { let q = &queries[head]; let diff = q.time - prev_reverse; let at0= if q.initial < argmin { min_sand } else if argmax < q.initial { max_sand } else { min_sand + q.initial - argmin }; let to = min(x, max(0, at0 + diff * incr)); answers[head] = to; head += 1; } let diff = next_reverse - prev_reverse; let to_min_sand = min_sand + diff * incr; let to_max_sand = max_sand + diff * incr; if to_min_sand < 0 { argmin -= to_min_sand; } if to_max_sand > x { argmax -= to_max_sand - x; } min_sand = min(x, max(0, to_min_sand)); max_sand = min(x, max(0, to_max_sand)); if min_sand == max_sand { argmin = x; argmax = x; } incr *= -1; } for a in answers { println!("{}", a); } }
Submission Info
Submission Time | |
---|---|
Task | F - Sandglass |
User | hamadu |
Language | Rust (1.15.1) |
Score | 700 |
Code Size | 3171 Byte |
Status | AC |
Exec Time | 217 ms |
Memory | 8184 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 700 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_000.txt, 0_001.txt, 0_002.txt |
All | 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_000.txt | AC | 2 ms | 4352 KB |
0_001.txt | AC | 2 ms | 4352 KB |
0_002.txt | AC | 2 ms | 4352 KB |
1_003.txt | AC | 188 ms | 6524 KB |
1_004.txt | AC | 196 ms | 6396 KB |
1_005.txt | AC | 197 ms | 8184 KB |
1_006.txt | AC | 189 ms | 6524 KB |
1_007.txt | AC | 191 ms | 6520 KB |
1_008.txt | AC | 196 ms | 8184 KB |
1_009.txt | AC | 189 ms | 6652 KB |
1_010.txt | AC | 196 ms | 6520 KB |
1_011.txt | AC | 217 ms | 8184 KB |
1_012.txt | AC | 192 ms | 6780 KB |
1_013.txt | AC | 195 ms | 6648 KB |
1_014.txt | AC | 197 ms | 8184 KB |
1_015.txt | AC | 196 ms | 6780 KB |
1_016.txt | AC | 209 ms | 6776 KB |
1_017.txt | AC | 197 ms | 8184 KB |
1_018.txt | AC | 192 ms | 6908 KB |
1_019.txt | AC | 196 ms | 6776 KB |
1_020.txt | AC | 199 ms | 8184 KB |
1_021.txt | AC | 194 ms | 6908 KB |
1_022.txt | AC | 196 ms | 6904 KB |
1_023.txt | AC | 201 ms | 8184 KB |
1_024.txt | AC | 199 ms | 6908 KB |
1_025.txt | AC | 198 ms | 6648 KB |
1_026.txt | AC | 200 ms | 8184 KB |
1_027.txt | AC | 199 ms | 6908 KB |
1_028.txt | AC | 198 ms | 6520 KB |
1_029.txt | AC | 202 ms | 8184 KB |
1_030.txt | AC | 200 ms | 6908 KB |
1_031.txt | AC | 199 ms | 6520 KB |
1_032.txt | AC | 201 ms | 8184 KB |
1_033.txt | AC | 188 ms | 7164 KB |
1_034.txt | AC | 192 ms | 7164 KB |
1_035.txt | AC | 198 ms | 6648 KB |
1_036.txt | AC | 193 ms | 7164 KB |
1_037.txt | AC | 190 ms | 7292 KB |
1_038.txt | AC | 200 ms | 8184 KB |
1_039.txt | AC | 196 ms | 7036 KB |
1_040.txt | AC | 193 ms | 7292 KB |
1_041.txt | AC | 201 ms | 8184 KB |