fork download
copy 
  1. #[allow(unused_imports)]
  2. use std::io::{BufWriter, stdin, stdout, Write};
  3.  
  4. #[derive(Default)]
  5. struct Scanner { buf: Vec<String> }
  6. impl Scanner {
  7.     fn next<T: std::str::FromStr>(&mut self) -> T {
  8.         loop {
  9.             if let Some(tok) = self.buf.pop() {
  10.                 return tok.parse().ok().unwrap();
  11.             }
  12.             let mut s = String::new();
  13.             stdin().read_line(&mut s).unwrap();
  14.             self.buf = s.split_whitespace().rev().map(String::from).collect();
  15.         }
  16.     }
  17. }
  18.  
  19. macro_rules! io_init {
  20.     ($scan:ident, $out:ident) => {
  21.         let mut $scan = Scanner::default();
  22.         let mut $out = BufWriter::new(stdout());
  23.     };
  24. }
  25.  
  26. macro_rules! read {
  27.     ($scan:ident, $($v:ident=>$t:ty),*) => {
  28.         $(let $v = $scan.next::<$t>();)*
  29.     };
  30. }
  31.  
  32. const LOG: usize = 20;
  33.  
  34. fn slv(scan: &mut Scanner, out: &mut BufWriter<std::io::Stdout>) {
  35.     read!(scan, n=>usize);
  36.     let mut a = vec![0i64; n+2];
  37.     for i in 1..=n {
  38.         a[i] = scan.next();
  39.     }
  40.     let mut lg = vec![0usize; n+2];
  41.     for i in 2..=n {
  42.         lg[i] = lg[i>>1] + 1;
  43.     }
  44.     let mut lf  = vec![[0usize; LOG]; n+2];
  45.     let mut rg  = vec![[0usize; LOG]; n+2];
  46.     let mut lf1 = vec![[0usize; LOG]; n+2];
  47.     let mut rg1 = vec![[0usize; LOG]; n+2];
  48.     let mut st = Vec::new();
  49.  
  50.     st.clear();
  51.     for i in 1..=n {
  52.         while st.last().map_or(false, |&j| a[j] > a[i]) { st.pop(); }
  53.         lf[i][0] = *st.last().unwrap_or(&0);
  54.         st.push(i);
  55.     }
  56.     for j in 1..LOG {
  57.         for i in 1..=n {
  58.             lf[i][j] = lf[ lf[i][j-1] ][j-1];
  59.         }
  60.     }
  61.  
  62.     st.clear();
  63.     for i in 1..=n {
  64.         while st.last().map_or(false, |&j| a[j] < a[i]) { st.pop(); }
  65.         lf1[i][0] = *st.last().unwrap_or(&0);
  66.         st.push(i);
  67.     }
  68.     for j in 1..LOG {
  69.         for i in 1..=n {
  70.             lf1[i][j] = lf1[ lf1[i][j-1] ][j-1];
  71.         }
  72.     }
  73.  
  74.     st.clear();
  75.     for i in (1..=n).rev() {
  76.         while st.last().map_or(false, |&j| a[j] > a[i]) { st.pop(); }
  77.         rg[i][0] = *st.last().unwrap_or(&(n+1));
  78.         st.push(i);
  79.     }
  80.     for j in 1..LOG {
  81.         for i in 1..=n {
  82.             rg[i][j] = rg[ rg[i][j-1] ][j-1];
  83.         }
  84.     }
  85.  
  86.     st.clear();
  87.     for i in (1..=n).rev() {
  88.         while st.last().map_or(false, |&j| a[j] < a[i]) { st.pop(); }
  89.         rg1[i][0] = *st.last().unwrap_or(&(n+1));
  90.         st.push(i);
  91.     }
  92.     for j in 1..LOG {
  93.         for i in 1..=n {
  94.             rg1[i][j] = rg1[ rg1[i][j-1] ][j-1];
  95.         }
  96.     }
  97.  
  98.     let mut tr = vec![0usize; n+1];
  99.  
  100.     for i in 1..=n {
  101.         let mut l = 1;
  102.         let mut r = i;
  103.         let mut ans = i;
  104.         while l <= r {
  105.             let mid = (l + r) >> 1;
  106.             let d = lg[i-mid];
  107.             let mut c = 0;
  108.             let mut now = i;
  109.             for j in (0..=d).rev() {
  110.                 let p = lf[now][j];
  111.                 if p >= mid {
  112.                     c += 1 << j;
  113.                     now = p;
  114.                 }
  115.             }
  116.             now = i;
  117.             for j in (0..=d).rev() {
  118.                 let p = lf1[now][j];
  119.                 if p >= mid {
  120.                     c += 1 << j;
  121.                     now = p;
  122.                 }
  123.             }
  124.             if c == i-mid {
  125.                 ans = mid;
  126.                 r = mid - 1;
  127.             } else {
  128.                 l = mid + 1;
  129.             }
  130.         }
  131.         let mut l = i;
  132.         let mut r = n;
  133.         let mut ans1 = i;
  134.         while l <= r {
  135.             let mid = (l + r) >> 1;
  136.             let d = lg[mid-i];
  137.             let mut c = 0;
  138.             let mut now = i;
  139.             for j in (0..=d).rev() {
  140.                 let p = rg[now][j];
  141.                 if p <= mid {
  142.                     c += 1 << j;
  143.                     now = p;
  144.                 }
  145.             }
  146.             now = i;
  147.             for j in (0..=d).rev() {
  148.                 let p = rg1[now][j];
  149.                 if p <= mid {
  150.                     c += 1 << j;
  151.                     now = p;
  152.                 }
  153.             }
  154.             if c == mid - i {
  155.                 ans1 = mid;
  156.                 l = mid + 1;
  157.             } else {
  158.                 r = mid - 1;
  159.             }
  160.         }
  161.         tr[ans] = tr[ans].max(ans1);
  162.     }
  163.  
  164.     for i in 1..=n {
  165.         tr[i] = tr[i].max(tr[i-1]);
  166.     }
  167.     let mut s = 0u64;
  168.     for i in 1..=n {
  169.         s += (tr[i] - i + 1) as u64;
  170.     }
  171.     writeln!(out, "{}", s).unwrap();
  172. }
  173.  
  174. fn main(){
  175.     io_init!(scan,out);
  176.     read!(scan, tc=>usize);
  177.     for _ in 0..tc {
  178.         slv(&mut scan, &mut out);
  179.     }
  180. }
  181.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
5
3
3 1 2
5
2 3 4 5 1
4
3 4 1 2
7
1 2 3 4 5 6 7
10
7 8 2 4 5 10 1 3 6 9
stdout
copy 
6
15
9
28
36
https://ideone.com/wk3DNh
language:
Rust (rust 1.56)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!