結果

問題 No.3116 More and more teleporter
ユーザー かえる☔
提出日時 2025-04-20 18:06:27
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 5,928 bytes
コンパイル時間 12,601 ms
コンパイル使用メモリ 401,864 KB
実行使用メモリ 12,496 KB
最終ジャッジ日時 2025-04-20 18:06:44
合計ジャッジ時間 16,773 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_imports, non_snake_case, dead_code, unused_macros)]
use std::{collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque as Deque}, default::Default, io::Write, mem::swap};
use proconio::{input, marker::Usize1 as usize1, marker::Chars as chars};

macro_rules! chmax {
    ($target:expr, $value:expr) => {
        if $target < $value {
            $target = $value;
            true
        } else {false}
    };
}
macro_rules! chmin {
    ($target:expr, $value:expr) => {
        if $target > $value {
            $target = $value;
            true
        } else {false}
    };
}

fn yn(x: bool) {
    if x {
        println!("Yes")
    } else {
        println!("No")
    }
}

fn extend_euclid(a: i64, b: i64) -> Result<(i64, i64), i64> {
    /*
    ax+by=1 を満たすOk((x, y))を返す。存在しなければErr(gcd(a, b))を返す。
     */
    fn inner(a: i64, b: i64, ae: (i64, i64), be: (i64, i64)) -> Result<(i64, i64), i64> {
        if b == 0 {
            if a == 1 {
                return Ok(ae);
            } else {
                return Err(a);
            }
        }
        let mut new_be = (0, 0);
        new_be.0 = ae.0 - a / b * be.0;
        new_be.1 = ae.1 - a / b * be.1;
        inner(b, a%b, be, new_be)
    }
    inner(a, b, (1, 0), (0, 1))
}


#[derive(Debug)]
struct DisjointSetUnion {
    parents: Vec<usize>,
    children: Vec<Vec<usize>>,
    sizes: Vec<usize>,
}
impl DisjointSetUnion {
    fn new(N: usize) -> Self {
        let parents = (0..N).collect();
        let children = vec![vec![]; N];
        let sizes = vec![1; N];
        Self { parents, children, sizes }
    }
    fn root(&self, x: usize) -> usize {
        if self.parents[x] == x {
            x
        } else {
            self.root(self.parents[x])
        }
    }
    fn size(&self, x: usize) -> usize {
        self.sizes[self.root(x)]
    }
    fn union(&mut self, a: usize, b: usize) -> bool {
        let (a, b) = (self.root(a), self.root(b));
        if a==b {
            return false;
        }
        if self.size(a) > self.size(b) {
            self.parents[b] = a;
            self.children[a].push(b);
            self.sizes[a] += self.sizes[b];
            self.sizes[b] = 0;
        } else {
            self.parents[a] = b;
            self.children[b].push(a);
            self.sizes[b] += self.sizes[a];
            self.sizes[a] = 0;
        }
        true
    }
    fn connections(&self) -> Vec<usize> {
        let mut res = Vec::new();
        for i in 0..self.parents.len() {
            if self.root(i) == i {
                res.push(i)
            }
        }
        res
    }
}

struct SegTree<T: Copy> {
    size: usize,
    dat: Vec<T>,
    update_func: Box<dyn Fn(T, T) -> T>,
    identity: T,
}
impl<T: Copy> SegTree<T> {
    fn new(size: usize, update_func: impl Fn(T, T) -> T + 'static, identity: T) -> Self {
        let size = size.next_power_of_two();
        let dat = vec![identity.clone(); size*2-1];
        Self {
            size, dat, update_func: Box::new(update_func), identity,
        }
    }
    fn update(&mut self, mut i: usize, x: T) {
        i += self.size-1;
        self.dat[i] = x;
        while i > 0 {
            i = (i-1)/2;
            self.dat[i] = (self.update_func)(self.dat[i*2+1], self.dat[i*2+2]);
        }
    }
    fn query(&self, a: usize, b: usize) -> T {
        self.query_sub(a, b, 0, 0, self.size)
    }
    fn query_sub(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> T {
        if r <= a || b <= l {
            self.identity
        } else if a <= l && r <= b {
            self.dat[k]
        } else {
            (self.update_func)(self.query_sub(a, b, k*2+1, l, (l+r)/2), self.query_sub(a, b, k*2+2, (l+r)/2, r))
        }
    }
}
impl SegTree<i64> {
    fn new_rminq(size: usize) -> Self {
        Self::new(size, i64::min, std::i64::MAX)
    }
    fn new_rmaxq(size: usize) -> Self {
        Self::new(size, i64::max, std::i64::MIN)
    }
    fn new_rsq(size: usize) -> Self {
        Self::new(size, |a, b| a+b, 0)
    }
}
impl SegTree<usize> {
    fn new_rminq(size: usize) -> Self {
        Self::new(size, usize::min, std::usize::MAX)
    }
    fn new_rmaxq(size: usize) -> Self {
        Self::new(size, usize::max, std::usize::MIN)
    }
    fn new_rsq(size: usize) -> Self {
        Self::new(size, |a, b| a+b, 0)
    }
}


fn around(i: usize, j: usize, H: usize, W: usize) -> Vec<(usize, usize)> {
    let mut res = vec![];

    if i!=0 {
        res.push((i-1, j));
    }
    if j!=0 {
        res.push((i, j-1));
    }
    if i!=H-1 {
        res.push((i+1, j));
    }
    if j!=W-1 {
        res.push((i, j+1))
    }
    res
}
fn to_index(i: usize, j: usize, W: usize) -> usize {
    i*W+j
}



fn lowerchar2code(c: char) -> usize {
    c as usize - 'a' as usize
}



type ModType = i64;
static MOD: ModType = 1000000007;

fn pow(base: ModType, power: ModType, modulo: ModType) -> ModType {
    if power == 0 {
        1
    } else if power == 1 {
        base % modulo
    } else {
        if power % 2 == 0 {
           pow(base, power/2, modulo).pow(2) % modulo
       } else {
           let tmp = pow(base, power/2, modulo).pow(2) % modulo;
           tmp * base % modulo
       }
    }
}

fn recip(x: ModType) -> ModType {
    pow(x, MOD-2, MOD)
}


fn main() {
    input! {
        N: usize, Q: usize,
    }

    let mut left = SegTree::<i64>::new_rminq(N);
    let mut right = SegTree::<i64>::new_rminq(N);

    for _i in 0..Q {
        input!{q: usize, x: usize1};
        if q == 1 {
            let mut ans = x as i64;
            if left.query(0, x) != i64::MAX {
                chmin!(ans , x as i64 - left.query(0, x));
            }
            chmin!(ans, right.query(x+1, N) - x as i64);
            println!("{}", ans);
        } else {
            input! {c: i64};
            left.update(x, (x as i64)-c);
            right.update(x, (x as i64)+c);
        }
    }
}
0