CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Kyselyt
Sender:Hennkka
Submission time:2020-10-18 11:40:42 +0300
Language:Rust
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED34
#3ACCEPTED54
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.48 s2, 3details
#3ACCEPTED0.48 s3details
#4ACCEPTED0.58 s3details
#5ACCEPTED0.46 s3details

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 table
    let mut sums = vec![0; (2 + n) * MAX_JUMPS];
    for i in 1..=n + 1 {
        sums[i] = sums[i - 1] + input[i];
    }

    // Compute forward jumps
    let 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
...

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
...

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
...

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
...

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
...