Task: | Kyselyt |
Sender: | Hennkka |
Submission time: | 2020-10-18 11:40:42 +0300 |
Language: | Rust |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 12 |
#2 | ACCEPTED | 34 |
#3 | ACCEPTED | 54 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.48 s | 2, 3 | details |
#3 | ACCEPTED | 0.48 s | 3 | details |
#4 | ACCEPTED | 0.58 s | 3 | details |
#5 | ACCEPTED | 0.46 s | 3 | details |
Compiler report
warning: unused import: `std::ops::*` --> input/code.rs:3:5 | 3 | use std::ops::*; | ^^^^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default warning: unused variable: `n` --> input/code.rs:8:9 | 8 | let n = input.len(); | ^ help: consider prefixing with an underscore: `_n` | = note: `#[warn(unused_variables)]` on by default warning: unused variable: `n` --> input/code.rs:95:9 | 95 | let n: usize = nq.next().unwrap(); | ^ help: consider prefixing with an underscore: `_n` warning: function is never used: `solve_brute` --> input/code.rs:7:4 | 7 | fn solve_brute(input: Vec<u64>, queries: Vec<(usize, usize)>) -> Vec<u64> { | ^^^^^^^^^^^ | = note: `#[warn(dead_code)]` on by default
Code
use std::io::BufRead;use std::iter::*;use std::ops::*;const MAX_JUMPS: usize = 20;fn solve_brute(input: Vec<u64>, queries: Vec<(usize, usize)>) -> Vec<u64> {let n = input.len();let input: Vec<_> = once(1_000_000_000).chain(input.into_iter()).collect();queries.into_iter().map(|(a, b)| {let mut h = input[a];let mut res = 0;for i in a..=b {if input[i] < h {res += h - input[i];} else {h = input[i];}}res}).collect()}fn solve(input: Vec<u64>, queries: Vec<(usize, usize)>) -> Vec<u64> {let n = input.len();let input: Vec<_> = once(1_000_000_000_000).chain(input.into_iter()).chain(once(1_000_000_000_000)).collect();// Compute sum tablelet mut sums = vec![0; (2 + n) * MAX_JUMPS];for i in 1..=n + 1 {sums[i] = sums[i - 1] + input[i];}// Compute forward jumpslet mut forward_jump_targets = vec![0; (2 + n) * MAX_JUMPS];let mut forward_jump_costs = vec![0; (2 + n) * MAX_JUMPS];{let mut ends = vec![n + 1];for i in (1..=n).rev() {while input[*ends.last().unwrap()] <= input[i] {ends.pop();}let target = *ends.last().unwrap();forward_jump_targets[i * MAX_JUMPS + 0] = target;forward_jump_costs[i * MAX_JUMPS + 0] =input[i] * ((target - i - 1) as u64) - (sums[target - 1] - sums[i]);ends.push(i);}forward_jump_targets[(n + 1) * MAX_JUMPS + 0] = n + 1;for length in 1..MAX_JUMPS {forward_jump_targets[(n + 1) * MAX_JUMPS + length] = n + 1;for i in 1..=n {let t1 = forward_jump_targets[i * MAX_JUMPS + length - 1];let t2 = forward_jump_targets[t1 * MAX_JUMPS + length - 1];forward_jump_targets[i * MAX_JUMPS + length] = t2;forward_jump_costs[i * MAX_JUMPS + length] = forward_jump_costs[i * MAX_JUMPS + length - 1]+ forward_jump_costs[t1 * MAX_JUMPS + length - 1];}}}queries.into_iter().map(|(a, b)| {let mut res = 0;let mut cur = a;for length in (0..MAX_JUMPS).rev() {while forward_jump_targets[cur * MAX_JUMPS + length] <= b {res += forward_jump_costs[cur * MAX_JUMPS + length];cur = forward_jump_targets[cur * MAX_JUMPS + length];}}if cur < b {res += ((b - cur) as u64) * input[cur] - (sums[b] - sums[cur]);}res}).collect()}fn main() {let stdin = std::io::stdin();let stdin = stdin.lock();let mut lines = stdin.lines();let nq = lines.next().unwrap().unwrap();let mut nq = nq.split_whitespace().map(|v| v.parse().unwrap());let n: usize = nq.next().unwrap();let q: usize = nq.next().unwrap();let input = lines.next().unwrap().unwrap().split_whitespace().map(|v| v.parse().unwrap()).collect();let queries = lines.take(q).map(|line| {line.unwrap().split_whitespace().map(|v| v.parse().unwrap()).collect::<Vec<_>>()}).map(|v| (v[0], v[1])).collect();for res in solve(input, queries) {println!("{}", res);}}#[cfg(test)]mod tests {use super::*;fn construct_queries(n: usize) -> Vec<(usize, usize)> {let mut res = vec![];for a in 1..=n {for b in a..=n {res.push((a, b));}}res}#[test]fn test_sample() {assert_eq!(solve(vec![2, 10, 4, 2, 5], vec![(3, 5), (2, 2), (1, 4)]),vec![2, 0, 14]);}#[test]fn test_manual() {let arr = vec![5, 10, 5, 2, 6, 11, 8, 10, 2, 1, 0, 3, 4];assert_eq!(solve(arr.clone(), construct_queries(arr.len())),solve_brute(arr.clone(), construct_queries(arr.len())),);}#[test]fn test_semi_increasing() {let arr = vec![0, 2, 1, 4, 3, 6, 5, 8, 7, 10, 9];assert_eq!(solve(arr.clone(), construct_queries(arr.len())),solve_brute(arr.clone(), construct_queries(arr.len())),);}#[test]fn test_semi_decreasing() {let mut arr = vec![0, 2, 1, 4, 3, 6, 5, 8, 7, 10, 9];arr.reverse();assert_eq!(solve(arr.clone(), construct_queries(arr.len())),solve_brute(arr.clone(), construct_queries(arr.len())),);}#[test]fn test_smallish_random() {use rand::{distributions::uniform::Uniform, prelude::*};let mut rng = rand::thread_rng();let n = 200_000;let q = 200;let input_dist = Uniform::new_inclusive(0, 1_000_000_000);let query_dist = Uniform::new_inclusive(1, n);let input: Vec<_> = repeat_with(|| rng.sample(input_dist)).take(n).collect();let queries: Vec<_> = repeat_with(|| (rng.sample(query_dist), rng.sample(query_dist))).map(|(a, b)| if a <= b { (a, b) } else { (b, a) }).take(q).collect();assert_eq!(solve(input.clone(), queries.clone()),solve_brute(input, queries));}#[test]fn test_large() {use rand::{distributions::uniform::Uniform, prelude::*};let mut rng = rand::thread_rng();let n = 200_000;let q = 200_000;let input_dist = Uniform::new_inclusive(0, 1_000_000_000);let query_dist = Uniform::new_inclusive(1, n);let input: Vec<_> = repeat_with(|| rng.sample(input_dist)).take(n).collect();let queries: Vec<_> = repeat_with(|| (rng.sample(query_dist), rng.sample(query_dist))).map(|(a, b)| if a <= b { (a, b) } else { (b, a) }).take(q).collect();solve(input, queries);}}
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
100 100 70 8 72 88 42 78 85 41 23 36 6... |
correct output |
---|
99 0 922 2579 1892 ... |
user output |
---|
99 0 922 2579 1892 ... Truncated |
Test 2
Group: 2, 3
Verdict: ACCEPTED
input |
---|
200000 200000 98 99 29 92 29 81 100 52 89 80... |
correct output |
---|
1497732 2810356 9532632 6655773 5403513 ... |
user output |
---|
1497732 2810356 9532632 6655773 5403513 ... Truncated |
Test 3
Group: 3
Verdict: ACCEPTED
input |
---|
200000 200000 818377786 934884634 816080381 ... |
correct output |
---|
86877225712611 94684086875470 92703793485296 38149694892093 61948503092286 ... |
user output |
---|
86877225712611 94684086875470 92703793485296 38149694892093 61948503092286 ... Truncated |
Test 4
Group: 3
Verdict: ACCEPTED
input |
---|
200000 200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
0 0 0 0 0 ... |
user output |
---|
0 0 0 0 0 ... Truncated |
Test 5
Group: 3
Verdict: ACCEPTED
input |
---|
200000 200000 200000 199999 199998 199997 19... |
correct output |
---|
15920862903 3193483321 18874982071 4846348926 3970697055 ... |
user output |
---|
15920862903 3193483321 18874982071 4846348926 3970697055 ... Truncated |