Submission #1817491

---

Source Code Expand

#[allow(unused_macros)]
macro_rules! debug {
  ($($e:expr), *) => {println!(concat!($(stringify!($e), " = {:?}\n"), *), $($e), *)}
}

fn main() {
  let n = get::val::<usize>();
  let xs = get::list::<u64>();
  
  let mut xis = xs.iter().zip(0..).collect::<Vec<_>>();
  xis.sort();
  
  let mut uf = UnionFind::new(n);
  let mut ans: u64 = 0;
  for &(&x,i) in xis.iter().rev() {
    let l: u64 = if i==0 || xs[i-1] < x {0} else {
      let rk = uf.rank(i-1);
      uf.unite(i-1,i);
      rk as u64
    };
    let r: u64 = if i==n-1 || xs[i+1] < x {0} else {
      let rk = uf.rank(i+1);
      uf.unite(i,i+1);
      rk as u64
    };
    ans += x * (l + 1) * (r + 1)
  }
  
  println!("{}", ans)
}

#[allow(dead_code)]
struct UnionFind {
  size: usize,
  rp: Vec<usize>,
  rk: Vec<usize>
}

#[allow(dead_code)]
impl UnionFind {
  fn new(n: usize) -> UnionFind {
    UnionFind {
      size: n,
      rp: (0..n).collect(),
      rk: vec![1; n]
    }
  }

  fn rep(&self, p: usize) -> usize {
    if self.rp[p] == p {p} else {self.rep(self.rp[p])}
  }

  fn rank(&self, p: usize) -> usize {
    self.rk[self.rep(p)]
  }

  fn same(&self, p: usize, q: usize) -> bool {
    self.rep(p) == self.rep(q)
  }

  fn count(&self) -> usize {
    let mut reps = (0..self.size).map(|x|self.rep(x)).collect::<Vec<_>>();
    reps.sort();
    reps.dedup();
    reps.len()
  }

  fn unite(&mut self, p: usize, q:usize) {
    let repp = self.rep(p);
    let repq = self.rep(q);
    if repp == repq {return}

    let rkp = self.rk[repp];
    let rkq = self.rk[repq];
    let (p, repp, repq) = if rkp <= rkq {(p, repp, repq)} else {(q, repq, repp)};

    self.rp[p] = repq;
    self.rp[repp] = repq;
    self.rk[repq] += self.rk[repp];
  }
}

#[allow(dead_code)]
mod get {
  use std::io::*;
  use std::str::*;

  pub fn val<T: FromStr>() -> T {
    let mut buf = String::new();
    let s = stdin();
    s.lock().read_line(&mut buf).ok();
    buf.trim_right().parse::<T>().ok().unwrap()
  }

  pub fn vals<T: FromStr>(n: usize) -> Vec<T> {
    let mut vec: Vec<T> = vec![];
    for _ in 0 .. n {
      vec.push(val());
    }
    vec
  }

  pub fn tuple<T1: FromStr, T2: FromStr>() -> (T1, T2) {
    let mut buf = String::new();
    let s = stdin();
    s.lock().read_line(&mut buf).ok();
    let mut it = buf.trim_right().split_whitespace();
    let x = it.next().unwrap().parse::<T1>().ok().unwrap();
    let y = it.next().unwrap().parse::<T2>().ok().unwrap();
    (x, y)
  }

  pub fn tuples<T1: FromStr, T2: FromStr>(n: usize) -> Vec<(T1, T2)> {
    let mut vec: Vec<(T1, T2)> = vec![];
    for _ in 0 .. n {
      vec.push(tuple());
    }
    vec
  }

  pub fn tuple3<T1: FromStr, T2: FromStr, T3: FromStr>() -> (T1, T2, T3) {
    let mut buf = String::new();
    let s = stdin();
    s.lock().read_line(&mut buf).ok();
    let mut it = buf.trim_right().split_whitespace();
    let x = it.next().unwrap().parse::<T1>().ok().unwrap();
    let y = it.next().unwrap().parse::<T2>().ok().unwrap();
    let z = it.next().unwrap().parse::<T3>().ok().unwrap();
    (x, y, z)
  }

  pub fn tuple3s<T1: FromStr, T2: FromStr, T3: FromStr>(n: usize) -> Vec<(T1, T2, T3)> {
    let mut vec: Vec<(T1, T2, T3)> = vec![];
    for _ in 0 .. n {
      vec.push(tuple3());
    }
    vec
  }

  pub fn list<T: FromStr>() -> Vec<T> {
    let mut buf = String::new();
    let s = stdin();
    s.lock().read_line(&mut buf).ok();
    buf.trim_right().split_whitespace().map(|t| t.parse::<T>().ok().unwrap()).collect()
  }

  pub fn lists<T: FromStr>(h: usize) -> Vec<Vec<T>> {
    let mut mat: Vec<Vec<T>> = vec![];
    for _ in 0 .. h {
      mat.push(list());
    }
    mat
  }

  pub fn chars() -> Vec<char> {
    let mut buf = String::new();
    let s = stdin();
    s.lock().read_line(&mut buf).ok();
    buf.trim_right().chars().collect()
  }
}

Submission Info

Judge Result