Submission #1662761

---

Source Code Expand

use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;


fn main(){
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    while let Some(n) = sc.read1() {
        let mut xs = vec![];
        for _ in 0..n {
            let x: i64 = sc.read();
            xs.push(x);
        }
        let xs = xs;

        // calculate ascending subsequence
        let mut ascending = vec![(0, std::usize::MAX)];
        for (i, &x) in xs.iter().enumerate() {
            if x > ascending.last().unwrap().0 {
                ascending.push((x, i));
            }
        }

        let k = ascending.len();
        let mut res = vec![0; n];
        let mut partial_sum = vec![0; k];
        for x in xs {
            // binary search...
            let mut lo = 0;
            let mut hi = k;
            while hi - lo > 1 {
                let mid = (lo + hi) / 2;
                if x < ascending[mid].0 {
                    hi = mid;
                } else {
                    lo = mid;
                }
            }
            assert!(ascending[lo].0 <= x);
            assert!(hi == k || x < ascending[hi].0);

            res[ascending[lo].1] += x - ascending[lo].0;
            if lo > 0 {
                partial_sum[lo - 1] += 1;
            }
        }

        for j in (1..k).rev() {
            partial_sum[j - 1] += partial_sum[j];
        }

        for j in 1..k {
            let gain = partial_sum[j - 1] * (ascending[j].0 - ascending[j - 1].0);
            res[ascending[j].1] += gain;
        }

        for r in res {
            println!("{}", r);
        }
    }
}

//=============================================================================

struct Scanner<'a> {
    cin: StdinLock<'a>,
}

impl<'a> Scanner<'a> {
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner { cin: cin }
    }

    fn read1<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        token.parse::<T>().ok()
    }

    fn read<T: FromStr>(&mut self) -> T {
        self.read1().unwrap()
    }
}

Submission Info

Judge Result