結果

問題 No.1558 Derby Live
ユーザー akakimidoriakakimidori
提出日時 2021-06-26 00:29:53
言語 Rust
(1.77.0)
結果
AC  
実行時間 49 ms / 2,000 ms
コード長 4,767 bytes
コンパイル時間 1,103 ms
コンパイル使用メモリ 152,756 KB
実行使用メモリ 4,732 KB
最終ジャッジ日時 2023-09-07 15:12:37
合計ジャッジ時間 5,002 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
4,376 KB
testcase_01 AC 49 ms
4,728 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 31 ms
4,380 KB
testcase_04 AC 13 ms
4,380 KB
testcase_05 AC 16 ms
4,380 KB
testcase_06 AC 25 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 25 ms
4,380 KB
testcase_09 AC 26 ms
4,380 KB
testcase_10 AC 26 ms
4,380 KB
testcase_11 AC 27 ms
4,380 KB
testcase_12 AC 27 ms
4,376 KB
testcase_13 AC 30 ms
4,380 KB
testcase_14 AC 32 ms
4,380 KB
testcase_15 AC 35 ms
4,732 KB
testcase_16 AC 36 ms
4,716 KB
testcase_17 AC 37 ms
4,720 KB
testcase_18 AC 38 ms
4,708 KB
testcase_19 AC 40 ms
4,712 KB
testcase_20 AC 41 ms
4,708 KB
testcase_21 AC 38 ms
4,724 KB
testcase_22 AC 40 ms
4,708 KB
testcase_23 AC 41 ms
4,712 KB
testcase_24 AC 38 ms
4,668 KB
testcase_25 AC 40 ms
4,704 KB
testcase_26 AC 41 ms
4,716 KB
testcase_27 AC 40 ms
4,700 KB
testcase_28 AC 40 ms
4,712 KB
testcase_29 AC 41 ms
4,712 KB
testcase_30 AC 38 ms
4,712 KB
testcase_31 AC 40 ms
4,712 KB
testcase_32 AC 41 ms
4,708 KB
testcase_33 AC 1 ms
4,380 KB
testcase_34 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// ---------- begin SegmentTree Point update Range query ----------
mod segment_tree {
    pub struct PURQ<T, F> {
        size: usize,
        data: Vec<T>,
        e: T,
        op: F,
    }
    #[allow(dead_code)]
    impl<T, F> PURQ<T, F>
    where
        T: Clone,
        F: Fn(&T, &T) -> T,
    {
        pub fn new(size: usize, e: T, op: F) -> PURQ<T, F> {
            let size = size.next_power_of_two();
            PURQ {
                size,
                data: vec![e.clone(); 2 * size],
                e: e,
                op: op,
            }
        }
        pub fn update(&mut self, x: usize, v: T) {
            assert!(x < self.size);
            let mut x = x + self.size;
            let data = &mut self.data;
            data[x] = v;
            x >>= 1;
            while x > 0 {
                data[x] = (self.op)(&data[2 * x], &data[2 * x + 1]);
                x >>= 1;
            }
        }
        pub fn update_tmp(&mut self, x: usize, v: T) {
            assert!(x < self.size);
            self.data[x + self.size] = v;
        }
        pub fn update_all(&mut self) {
            let data = &mut self.data;
            for k in (1..self.size).rev() {
                data[k] = (self.op)(&data[2 * k], &data[2 * k + 1]);
            }
        }
        pub fn find(&self, l: usize, r: usize) -> T {
            assert!(l <= r && r <= self.size);
            if l == r {
                return self.e.clone();
            }
            let mut p = self.e.clone();
            let mut q = self.e.clone();
            let mut l = l + self.size;
            let mut r = r + self.size;
            let data = &self.data;
            while l < r {
                if l & 1 == 1 {
                    p = (self.op)(&p, &data[l]);
                    l += 1;
                }
                if r & 1 == 1 {
                    r -= 1;
                    q = (self.op)(&data[r], &q);
                }
                l >>= 1;
                r >>= 1;
            }
            (self.op)(&p, &q)
        }
    }
}
// ---------- end SegmentTree Point update Range query ----------
// ---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
    use std::str::FromStr;
    pub struct Scanner<'a> {
        it: std::str::SplitWhitespace<'a>,
    }
    impl<'a> Scanner<'a> {
        pub fn new(s: &'a String) -> Scanner<'a> {
            Scanner {
                it: s.split_whitespace(),
            }
        }
        pub fn next<T: FromStr>(&mut self) -> T {
            self.it.next().unwrap().parse::<T>().ok().unwrap()
        }
        pub fn next_bytes(&mut self) -> Vec<u8> {
            self.it.next().unwrap().bytes().collect()
        }
        pub fn next_chars(&mut self) -> Vec<char> {
            self.it.next().unwrap().chars().collect()
        }
        pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
            (0..len).map(|_| self.next()).collect()
        }
    }
}
// ---------- end scannner ----------

use std::io::Write;

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut sc = scanner::Scanner::new(&s);
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    run(&mut sc, &mut out);
}

fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
    let n: usize = sc.next();
    let m: usize = sc.next();
    let q: usize = sc.next();
    const LEN: usize = 18;
    let mut ini = [0u8; LEN];
    for i in 0..LEN {
        ini[i] = i as u8;
    }
    let ini = ini;
    let mut seg = segment_tree::PURQ::new(m, ini, |a, b| {
        let mut c = [0; LEN];
        for (c, a) in c.iter_mut().zip(a) {
            *c = b[*a as usize];
        }
        c
    });
    for _ in 0..q {
        let op: u8 = sc.next();
        if op == 1 {
            let x = sc.next::<usize>() -1;
            let mut a = ini;
            for i in 0..n {
                let x = sc.next::<u8>() - 1;
                a[i] = x;
            }
            seg.update(x, a);
        } else if op == 2 {
            let s = sc.next::<usize>();
            let p = seg.find(0, s);
            let mut ans = [0; LEN];
            for i in 0..n {
                ans[p[i] as usize] = i + 1;
            }
            for (i, p) in ans.iter().enumerate().take(n) {
                write!(out, "{}{}", *p, [' ', '\n'][(i == n - 1) as usize]).ok();
            }
        } else {
            let l = sc.next::<usize>() - 1;
            let r = sc.next::<usize>();
            let p = seg.find(l, r);
            let ans = p.iter().enumerate().fold(0, |s, (i, &k)| s + i.max(k as usize) - i.min(k as usize));
            writeln!(out, "{}", ans).ok();
        }
    }
}
0