結果

問題 No.3116 More and more teleporter
コンテスト
ユーザー rhoo
提出日時 2025-04-18 22:34:54
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 114 ms / 2,000 ms
コード長 2,548 bytes
コンパイル時間 15,599 ms
コンパイル使用メモリ 388,908 KB
実行使用メモリ 33,252 KB
最終ジャッジ日時 2025-04-18 22:35:12
合計ジャッジ時間 18,370 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_imports,non_snake_case,dead_code)]
use std::{cmp::Reverse as Rev,collections::*,iter::*};
use proconio::{marker::*,*};


#[fastout]
fn main(){
    input!{
        n:usize,
        q:usize,
    }

    let mut qs=(0..q).map(|i|{
        let time=i+1;
        input!{t:usize}
        if t==1{
            input!{x:Usize1}
            Q{time,x,c:-1}
        } else{
            input!{x:Usize1,c:i64}
            Q{time,x,c}
        }
    }).collect::<Vec<_>>();
    qs.insert(0,Q{time:0,x:0,c:0});

    const INF:i64=i64::MAX/64;
    let mut ans=vec![INF;qs.len()];

    let mut todo=vec![vec![];n];
    let mut add=vec![vec![];n];

    for i in 0..qs.len(){
        if qs[i].c==-1{
            todo[qs[i].x].push(qs[i]);
        } else{
            add[qs[i].x].push(qs[i]);
        }
    }

    let mut set=BTreeMap::<usize,i64>::new();
    let mut rem=vec![];

    for i in 0..n{
        'a: for &Q{time,x,c} in &add[i]{
            let new=c-x as i64;
            if let Some((_,&pc))=set.range(..=time).rev().next(){
                if pc<=new{
                    continue 'a;
                }
            }

            rem.clear();
            for (&pt,&pc) in set.range(time..){
                if new<=pc{
                    rem.push(pt);
                }
            }

            for &t in &rem{
                set.remove(&t);
            }
            set.insert(time,new);
        }

        for &Q{time,x,..} in &todo[i]{
            if let Some((_,&nc))=set.range(..=time).rev().next(){
                ans[time]=ans[time].min(nc+x as i64);
            }
        }
    }

    set.clear();

    for i in (0..n).rev(){
        'a: for &Q{time,x,c} in &add[i]{
            let new=c-(n-x) as i64;
            if let Some((_,&pc))=set.range(..=time).rev().next(){
                if pc<=new{
                    continue 'a;
                }
            }

            rem.clear();
            for (&pt,&pc) in set.range(time..){
                if new<=pc{
                    rem.push(pt);
                }
            }

            for &t in &rem{
                set.remove(&t);
            }
            set.insert(time,new);
        }

        for &Q{time,x,..} in &todo[i]{
            if let Some((_,&nc))=set.range(..=time).rev().next(){
                ans[time]=ans[time].min(nc+(n-x) as i64);
            }
        }
    }

    for i in 0..qs.len(){
        if qs[i].c==-1{
            println!("{}",ans[i]);
        }
    }
}



#[derive(Clone,Copy)]
struct Q{
    time:usize,
    x:usize,
    c:i64,
}
0