#1045990 (Rust) No.3314 Library Rearrangement

• 問題: No.3314 Library Rearrangement
• ユーザー: 👑 ArcAki
• 提出日時: 2025-02-25 12:13:18
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 894 ms / 3,000 ms
• コード長: 11,031 bytes
• コンパイル時間: 13,023 ms
• コンパイル使用メモリ: 400,272 KB
• 実行使用メモリ: 20,636 KB
• 最終ジャッジ日時: 2025-05-06 07:05:53
• 合計ジャッジ時間: 37,269 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 2
other	AC * 39

ソースコード

#[allow(unused_imports)]
use std::{
    cell::RefCell, convert::{Infallible, TryFrom, TryInto as _},
    fmt::{self, Debug, Display, Formatter,},
    fs::{File},
    hash::{Hash, Hasher},
    iter::{Product, Sum},
    marker::PhantomData,
    ops::{Add, AddAssign, Sub, SubAssign, Div, DivAssign, Mul, MulAssign, Neg, },
    str::FromStr,
    sync::{atomic::{self, AtomicU32, AtomicU64}, Once},
    collections::{*},
    mem::{swap},
    cmp::{self, Reverse, Ordering, Eq, PartialEq, PartialOrd},
    thread::LocalKey,
    f64::consts::PI,
    time::Instant,
    io::{self, stdin, Read, read_to_string, BufWriter, BufReader, stdout, Write},
};

#[allow(unused_imports)]
use proconio::{input, input_interactive, marker::{*}};
#[allow(unused_imports)]
//use rand::{thread_rng, Rng, seq::SliceRandom};
#[allow(unused_imports)]
//use ac_library::{*};

#[allow(dead_code)]
const INF: i64 = 1<<60;
#[allow(dead_code)]
const MOD: i64 = 998244353;
#[allow(dead_code)]
const D: [(usize, usize); 4] = [(1, 0), (0, 1), (!0, 0), (0, !0)];

pub fn bit_length(x: usize)->usize{
    64-x.saturating_sub(1).leading_zeros()as usize
}

pub trait SegtreeMonoid{
    type S: Clone+BeatsFail;
    fn identity()->Self::S;
    fn op(a: &Self::S, b: &Self::S)->Self::S;
}

pub trait LazySegtreeMonoid{
    type M: SegtreeMonoid;
    type F: Clone;
    fn id_e()-><Self::M as SegtreeMonoid>::S{<Self::M as SegtreeMonoid>::identity()}
    fn op(a: &<Self::M as SegtreeMonoid>::S, b: &<Self::M as SegtreeMonoid>::S)-><Self::M as SegtreeMonoid>::S{<Self::M>::op(a, b)}
    fn identity()->Self::F;
    fn map(f: &Self::F, x: &<Self::M as SegtreeMonoid>::S)-><Self::M as SegtreeMonoid>::S;
    fn composition(f: &Self::F, g: &Self::F)->Self::F;
}

pub trait BeatsFail{
    fn fail(&self) -> bool;
}

pub struct LazySegtree<F> where F: LazySegtreeMonoid{
    n: usize,
    log: usize,
    data: Vec<<F::M as SegtreeMonoid>::S>,
    lazy: Vec<F::F>,
}

impl<F: LazySegtreeMonoid> LazySegtree<F>{
    // 初期値開始
    pub fn new(n: usize)->Self{
        let n = n.next_power_of_two();
        let log = bit_length(n);
        let lazy = vec![F::identity(); n<<1];
        let data = vec![F::id_e(); n<<1];
        LazySegtree{
            n, log, data, lazy,
        }
    }

    // vectorを飲ませるならこっち。O(N)で初期化。
    pub fn build(vec: &Vec<<F::M as SegtreeMonoid>::S>)->Self {
        let n = vec.len().next_power_of_two();
        let log = bit_length(n);
        let lazy = vec![F::identity(); n<<1];
        let mut data = vec![F::id_e(); n<<1];
        data[n..(n+vec.len())].clone_from_slice(vec);
        let mut res = LazySegtree{
            n, log, data, lazy,
        };
        for i in (1..n).rev(){
            res.update(i);
        }
        res
    }

    pub fn set(&mut self, mut p: usize, x: <F::M as SegtreeMonoid>::S){
        p += self.n;
        for i in (1..=self.log).rev(){
            self.push(p>>i);
        }
        self.data[p] = x;
        for i in 1..=self.log{
            self.update(p>>i);
        }
    }

    // 下からデータ更新
    #[inline(always)]
    fn update(&mut self, k: usize){
        self.data[k] = F::op(&self.data[2*k], &self.data[2*k+1]);
    }

    // 遅延反映
    #[inline(always)]
    fn inner_apply(&mut self, k: usize, f: F::F){
        self.data[k] = F::map(&f, &self.data[k]);
        if k < self.n{
            self.lazy[k] = F::composition(&f, &self.lazy[k]);
            if self.data[k].fail(){
                self.push(k); self.update(k);
            }
        }
    }

    // 上から遅延更新
    #[inline(always)]
    fn push(&mut self, k: usize){
        self.inner_apply(2*k, self.lazy[k].clone());
        self.inner_apply(2*k+1, self.lazy[k].clone());
        self.lazy[k] = F::identity();
    }

    pub fn get(&mut self, mut p: usize)-><F::M as SegtreeMonoid>::S{
        p += self.n;
        for i in (1..self.log).rev(){
            self.push(p>>i);
        }
        self.data[p].clone()
    }

    // whileで打ち切った方が早そうだけどどうなんでしょう？
    #[inline]
    pub fn prod(&mut self, mut l: usize, mut r: usize)-><F::M as SegtreeMonoid>::S{
        if r<=l{return F::id_e()}
        l += self.n; r += self.n;
        for i in (1..=self.log).rev(){
            if ((l>>i)<<i) != l{
                self.push(l>>i);
            }
            if ((r>>i)<<i) != r{
                self.push(r>>i);
            }
        }
        let mut acl = F::id_e();
        let mut acr = F::id_e();
        while l < r{
            if l&1 != 0{
                acl = F::op(&acl, &self.data[l]);
                l += 1;
            }
            if r&1 != 0{
                r -= 1;
                acr = F::op(&self.data[r], &acr);
            }
            l >>= 1; r >>= 1;
        }
        F::op(&acl, &acr)
    }

    pub fn all_prod(&mut self)-><F::M as SegtreeMonoid>::S{
        self.update(1);
        self.data[1].clone()
    }

    pub fn apply_range(&mut self, mut l: usize, mut r: usize, f: F::F){
        if l>=r{return;}
        l += self.n; r += self.n;
        for i in (1..=self.log).rev(){
            if ((l>>i)<<i)!=l{
                self.push(l>>i);
            }
            if ((r>>i)<<i)!=r{
                self.push((r-1)>>i);
            }
        }
        let left = l;
        let right = r;
        while l < r{
            if l&1!=0{
                self.inner_apply(l, f.clone());
                l += 1;
            }
            if r&1!=0{
                r -= 1;
                self.inner_apply(r, f.clone());
            }
            l >>= 1; r>>=1;
        }
        for i in 1..=self.log{
            if ((left>>i)<<i)!=left{
                self.update(left>>i);
            }
            if ((right>>i)<<i)!=right{
                self.update((right-1)>>i);
            }
        }
    }

    pub fn max_right<G>(&mut self, mut l: usize, g: G)->usize
    where G: Fn(<F::M as SegtreeMonoid>::S)->bool{
        assert!(g(F::id_e()));
        if l >= self.n{return self.n}
        l += self.n;
        for i in 1..=self.log{
            self.push(l>>i);
        }
        let mut ac = F::id_e();
        while {
            while l%2==0{
                l>>=1;
            }
            if !g(F::op(&ac, &self.data[l])){
                while l < self.n{
                    self.push(l);
                    l *= 2;
                    let res = F::op(&ac, &self.data[l]);
                    if g(res.clone()){
                        ac = res;
                        l += 1;
                    }
                }
                return l-self.n;
            }
            ac = F::op(&ac, &self.data[l]);
            l += 1;
            let left = l as isize;
            (left&-left)!=left
        } {}
        self.n
    }

    pub fn min_left<G>(&mut self, mut r: usize, g: G)->usize
    where G: Fn(<F::M as SegtreeMonoid>::S)->bool{
        assert!(g(F::id_e()));
        if r==0{return 0;}
        r += self.n;
        for i in (1..=self.log).rev(){
            self.push((r-1)>>i);
        }
        let mut ac = F::id_e();
        while {
            r -= 1;
            while r%2 != 0{
                r >>= 1;
            }
            if !g(F::op(&self.data[r], &ac)){
                while r < self.n{
                    self.push(r);
                    r = 2*r+1;
                    let res = F::op(&self.data[r], &ac);
                    if g(res.clone()){
                        ac = res;
                        r -= 1;
                    }
                }
                return r+1-self.n;
            }
            ac = F::op(&self.data[r], &ac);
            let right = r as isize;
            (right&-right)!=right
        } {}
        0
    }

    pub fn get_slice(&mut self, mut l: usize, mut r: usize)->Vec<<F::M as SegtreeMonoid>::S>{
        l += self.n; r += self.n;
        for i in 1..self.n {
            self.push(i)
        }
        (l..r).into_iter().map(|z| self.data[z].clone()).collect()
    }
}

#[derive(Clone, Copy, Debug)]
struct S{
    num: i64,
    ac: i64,
    mi: i64,
    mic: i64,
    smi: i64,
    fail: bool
}

impl S{
    #[inline(always)]
    fn new(x: i64, n: i64)->Self{
        S{
            num: n,
            ac: n*x,
            mi: x,
            mic: n,
            smi: INF,
            fail: false,
        }
    }
}

impl BeatsFail for S{
    #[inline(always)]
    fn fail(&self) -> bool {
        self.fail
    }
}

struct M;
impl SegtreeMonoid for M{
    type S = S;

    fn identity() -> Self::S {
        S{
            num: 0, ac: 0, mi: INF, mic: 0, smi: INF, fail: false,
        }
    }

    fn op(&a: &Self::S, &b: &Self::S) -> Self::S {
        let (mi, mic, smi) = if a.mi < b.mi{
            (a.mi, a.mic, a.smi.min(b.mi))
        } else if a.mi > b.mi {
            (b.mi, b.mic, a.mi.min(b.smi))
        } else {
            (a.mi, a.mic+b.mic, a.smi.min(b.smi))
        };
        S{
            num: a.num+b.num,
            ac: a.ac+b.ac,
            mi, mic, smi,
            fail: false,
        }
    }
}

struct MM;
impl LazySegtreeMonoid for MM{
    type M = M;
    type F = i64;

    fn identity() -> Self::F {
        -INF
    }

    fn map(&f: &Self::F, &x: &<Self::M as SegtreeMonoid>::S) -> <Self::M as SegtreeMonoid>::S {
        if x.num==0||f==-INF{
            return x;
        }
        let mut res = x;
        if f <= x.mi{
            return res;
        } else if res.mi*res.num==res.ac{
            res.ac += (f-res.mi)*res.num;
            res.mi = res.mi.max(f);
            return res;
        } else if f < res.smi{
            res.ac += (f-res.mi)*res.mic;
            res.mi = f;
            return res;
        }
        res.fail = true;
        res
    }

    fn composition(&f: &Self::F, &g: &Self::F) -> Self::F {
        f.max(g)
    }
}

use proconio::fastout;
#[fastout]
fn main(){
    input!{
        n: usize, k: usize, q: usize,
        a: [i64; n],
        update: [(Usize1, usize, i64); k],
        query: [(Usize1, usize, i64); q],
    }
    let mx = (k+3).next_power_of_two()-1;
    let mut b = vec![!0usize; q];
    let mut t = vec![mx; q];
    let base = a.iter().map(|&x| S::new(x, 1)).collect::<Vec<_>>();
    while b[0].wrapping_add(1) < t[0]{
        let mut qs = vec![Vec::new(); mx];
        for (i, &(l, r, x)) in query.iter().enumerate(){
            let m = (b[i].wrapping_add(t[i]))/2;
            qs[m].push((l, r, x, i));
        }
        let mut segtree = LazySegtree::<MM>::build(&base);
        for (i, vc) in qs.iter().enumerate(){
            if 0 < i && i <= k{
                let (l, r, x) = update[i-1];
                segtree.apply_range(l, r, x);
            }
            for &(l, r, x, idx) in vc{
                if segtree.prod(l, r).ac >= x{
                    t[idx] = i;
                } else {
                    b[idx] = i;
                }
            }
        }
    }
    for r in t{
        if r > k{
            println!("-1");
        } else {
            println!("{}", r);
        }
    }
}