Kyselyt

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

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 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED

Test 4

Group: 3

Verdict: ACCEPTED

Test 5

Group: 3

Verdict: ACCEPTED