#632845 (Rust) No.1435 Mmm......

• 問題: No.1435 Mmm......
• ユーザー: Strorkis
• 提出日時: 2021-03-21 18:46:41
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 39 ms / 2,000 ms
• コード長: 5,418 bytes
• コンパイル時間: 13,126 ms
• コンパイル使用メモリ: 403,952 KB
• 実行使用メモリ: 12,488 KB
• 最終ジャッジ日時: 2024-11-22 13:12:55
• 合計ジャッジ時間: 16,109 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	1 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	AC	1 ms; 5,248 KB
testcase_06	AC	15 ms; 10,156 KB
testcase_07	AC	17 ms; 10,584 KB
testcase_08	AC	19 ms; 11,060 KB
testcase_09	AC	19 ms; 10,832 KB
testcase_10	AC	17 ms; 10,368 KB
testcase_11	AC	17 ms; 10,312 KB
testcase_12	AC	16 ms; 10,276 KB
testcase_13	AC	16 ms; 10,144 KB
testcase_14	AC	11 ms; 6,632 KB
testcase_15	AC	21 ms; 11,176 KB
testcase_16	AC	18 ms; 10,640 KB
testcase_17	AC	12 ms; 6,820 KB
testcase_18	AC	20 ms; 11,216 KB
testcase_19	AC	16 ms; 10,380 KB
testcase_20	AC	19 ms; 11,000 KB
testcase_21	AC	33 ms; 12,224 KB
testcase_22	AC	39 ms; 10,764 KB
testcase_23	AC	24 ms; 12,308 KB
testcase_24	AC	25 ms; 12,404 KB
testcase_25	AC	24 ms; 12,400 KB
testcase_26	AC	24 ms; 12,488 KB
testcase_27	AC	25 ms; 12,392 KB

ソースコード

// reference: https://github.com/atcoder/ac-library
#[allow(dead_code)]
mod segtree {
    pub struct Segtree<T, O, E> {
        n: usize, len: usize, height: usize,
        op: O, e: E,
        node: Vec<T>,
    }

    impl<T, O, E> Segtree<T, O, E>
    where
        T: Clone + Copy,
        O: Fn(T, T) -> T, E: Fn() -> T,
    {
        pub fn new(n: usize, op: O, e: E) -> Self {
            let (mut len, mut height) = (1, 1);
            while len < n {
                len *= 2;
                height += 1;
            }
            let node = vec![e(); 2 * len];
            Self { n, len, height, op, e, node }
        }

        pub fn from(v: &[T], op: O, e: E) -> Self {
            let mut st = Self::new(v.len(), op, e);
            for i in 0..v.len() { st.node[i + st.len] = v[i]; }
            for i in (1..st.len).rev() { st.update(i); }
            st
        }

        fn update(&mut self, k: usize) {
            self.node[k] = (self.op)(self.node[2 * k], self.node[2 * k + 1]);
        }

        pub fn set(&mut self, mut p: usize, x: T) {
            assert!(p < self.n);
            p += self.len;
            self.node[p] = x;
            for i in 1..self.height { self.update(p >> i) };
        }

        pub fn get(&self, p: usize) -> T {
            assert!(p < self.n);
            self.node[p + self.len]
        }

        pub fn prod(&self, mut l: usize, mut r: usize) -> T {
            assert!(l <= r && r <= self.n);
            let (mut sml, mut smr) = ((self.e)(), (self.e)());
            l += self.len;
            r += self.len;

            while l < r {
                if l & 1 != 0 {
                    sml = (self.op)(sml, self.node[l]);
                    l += 1;
                }
                if r & 1 != 0 {
                    r -= 1;
                    smr = (self.op)(self.node[r], smr);
                }
                l >>= 1;
                r >>= 1;
            }

            (self.op)(sml, smr)
        }

        pub fn all_prod(&self) -> T {
            self.node[1]
        }

        pub fn max_right<F: Fn(T) -> bool>(&self, mut l: usize, f: F) -> usize {
            assert!(l <= self.n);
            assert!(f((self.e)()));
            if l == self.n { return self.n; }
            l += self.len;
            let mut sm = (self.e)();
            while {
                while l % 2 == 0 { l >>= 1; }
                if !f((self.op)(sm, self.node[l])) {
                    while l < self.len {
                        l = 2 * l;
                        if f((self.op)(sm, self.node[l])) {
                            sm = (self.op)(sm, self.node[l]);
                            l += 1;
                        }
                    }
                    return l - self.len;
                }
                sm = (self.op)(sm, self.node[l]);
                l += 1;
                (l & (!l + 1)) != l
            } {}
            self.n
        }

        pub fn min_left<F: Fn(T) -> bool>(&self, mut r: usize, f: F) -> usize {
            assert!(r <= self.n);
            assert!(f((self.e)()));
            if r == 0 { return 0; }
            r += self.len;
            let mut sm = (self.e)();
            while {
                r -= 1;
                while r > 1 && r % 2 != 0 { r >>= 1; }
                if !f((self.op)(self.node[r], sm)) {
                    while r < self.len {
                        r = 2 * r + 1;
                        if f((self.op)(self.node[r], sm)) {
                            sm = (self.op)(self.node[r], sm);
                            r -= 1;
                        }
                    }
                    return r + 1 - self.len;
                }
                sm = (self.op)(self.node[r], sm);
                (r & (!r + 1)) != r
            } {}
            0
        }
    }
}

use segtree::Segtree;

type T = [u32; 3];

const INF: u32 = 1 << 30;

fn run<'a, F: FnMut() -> &'a str, W: std::io::Write>(scan: &mut F, writer: &mut W) {
    macro_rules! scan {
        ([$t:tt; $n:expr]) => ((0..$n).map(|_| scan!($t)).collect::<Vec<_>>());
        (($($t:tt),*)) => (($(scan!($t)),*));
        (Usize1) => (scan!(usize) - 1);
        (Bytes) => (scan().as_bytes().to_vec());
        ($t:ty) => (scan().parse::<$t>().unwrap());
    }
    macro_rules! println {
        ($($arg:tt)*) => (writeln!(writer, $($arg)*).ok());
    }

    let n = scan!(usize);
    let a = scan!([u32; n]);

    let v = a.into_iter().map(|a| [a, INF, a]).collect::<Vec<_>>();
    let op = |a: T, b: T| {
        [
            a[0].min(b[0]),
            if a[0] < b[0] {
                *[a[1], b[0], b[1]].iter().min().unwrap()
            } else {
                *[a[0], a[1], b[1]].iter().min().unwrap()
            },
            a[2].max(b[2]),
        ]
    };
    let e = || [INF, INF, 0];
    let seg = Segtree::from(&v, op, e);

    let mut ans = 0;
    for l in 0..n {
        let f = |x: T| x[2] <= x[0] + x[1];
        let r = seg.max_right(l, f);
        ans += r - l - 1;
    }
    println!("{}", ans);
}

fn main() {
    let ref mut buf = Vec::new();
    std::io::Read::read_to_end(&mut std::io::stdin(), buf).ok();
    let mut iter = unsafe {
        std::str::from_utf8_unchecked(buf).split_ascii_whitespace()
    };
    let ref mut scan = || iter.next().unwrap();

    let stdout = std::io::stdout();
    let ref mut writer = std::io::BufWriter::new(stdout.lock());

    run(scan, writer);
}