AtCoder Beginner Contest 305 D

https://atcoder.jp/contests/abc305/tasks/abc305_d

開始時刻と終了時刻がAのどこに含まれるかを二分探索で特定します。

// Sleep Log
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

type Query = (i32, i32);

fn read_query() -> Query {
    let v = read_vec();
    (v[0], v[1])
}

fn read_input() -> (Vec<i32>, i32) {
    let _N: usize = read();
    let A = read_vec();
    let Q = read();
    (A, Q)
}

fn accumulate(A: &Vec<i32>) -> Vec<i32> {
    let mut B: Vec<i32> = vec![0];
    for i in (1..A.len()).step_by(2) {
        B.push(B.last().unwrap() + A[i+1] - A[i])
    }
    B
}

// find i s.t. A_i <= t < A_{i+1}
fn bin_search(t: i32, first: usize, last: usize, A: &Vec<i32>) -> usize {
    if last - first == 1 {
        first
    }
    else {
        let mid = (first + last) / 2;
        if A[mid] > t {
            bin_search(t, first, mid, &A)
        }
        else {
            bin_search(t, mid, last, &A)
        }
    }
}

fn sum_sleep_time(query: Query, A: &Vec<i32>, B: &Vec<i32>) -> i32 {
    let i = bin_search(query.0, 0, A.len(), &A);
    let j = bin_search(query.1, 0, A.len(), &A);
    let left = if i % 2 == 1 { A[i+1] - query.0 } else { 0 };
    let mid = B[j/2] - B[(i+1)/2];
    let right = if j % 2 == 1 { query.1 - A[j] } else { 0 };
    left + mid + right
}

fn f(A: Vec<i32>, Q: i32) {
    let B = accumulate(&A);
    for _ in 0..Q {
        let query = read_query();
        println!("{}", sum_sleep_time(query, &A, &B))
    }
}


//////////////////// main ////////////////////

fn main() {
    let (A, Q) = read_input();
    f(A, Q)
}