#1162718 (Rust) No.3530 「」

• 問題: No.3530 「」
• ユーザー: GaLLium
• 提出日時: 2026-05-04 12:58:09
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 582 ms / 3,000 ms
• コード長: 14,141 bytes
• コンパイル時間: 15,097 ms
• コンパイル使用メモリ: 202,696 KB
• 実行使用メモリ: 11,812 KB
• 最終ジャッジ日時: 2026-05-04 20:57:02
• 合計ジャッジ時間: 21,292 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_0

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

ソースコード

#![allow(unused)]
#![allow(non_snake_case)]
#![allow(dead_code)]

type Mint = ModInt998244353;
struct Additive;
impl Monoid for Additive{
    type S = Mint;
    fn identity() -> Self::S {Mint::new(0)}
    fn binary_operation(&a: &Self::S, &b: &Self::S) -> Self::S {a+b}
}
struct MulAdd;
impl MapMonoid for MulAdd{
    type M = Additive;
    type F = Mint;
    fn identity_map() -> Self::F {Mint::new(1)}
    fn mapping(&f: &Self::F, &a: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {f*a}
    fn composition(&f: &Self::F, &g: &Self::F) -> Self::F {f*g}
}

use proconio::input;
fn main(){
    input!{
        N:usize,
        mut Point: [(i64,i64);N],
    }
    let mut ans = Mint::new(0);
    
    //x座標
    Point.sort_by_key(|&(x,y)| x);
    //rank[i]:Point[i]が上から何番目の点か
    let mut yi = vec![];
    for i in 0..N{
        yi.push((Point[i].1,i));
    }
    yi.sort(); yi.reverse();
    let mut rank = vec![0usize;N];
    for r in 0..N{
        rank[yi[r].1] = r;
    }
    //prob[i]: 左ゾーンで一番下の「がrank[i]の点かつ，対応する」が存在しない確率
    let mut prob = LazySegtree::<MulAdd>::new(N+3);
    for i in 0..N{
        prob.set(i,(Mint::new(1)/Mint::new(4))*(Mint::new(3)/Mint::new(4)).pow(i as u64));
    }
    for i in (1..N).rev(){
        prob.apply_range(0..rank[i],Mint::new(3)/Mint::new(4));
        prob.set(rank[i],Mint::new(0));
        prob.apply_range(rank[i]+1..N,Mint::new(4)/Mint::new(3));
        ans += Mint::new(Point[i].0-Point[i-1].0)*(Mint::new(1)-prob.prod(0..N)-(Mint::new(3)/Mint::new(4)).pow(i as u64))
    }

    //y座標
    Point.sort_by_key(|&(x,y)| y);
    //rank[i]:Point[i]が右から何番目の点か
    let mut xi = vec![];
    for i in 0..N{
        xi.push((Point[i].0,i));
    }
    xi.sort(); xi.reverse();
    let mut rank = vec![0usize;N];
    for r in 0..N{
        rank[xi[r].1] = r;
    }
    //prob[i]: 下ゾーンで一番左の」がrank[i]の点かつ，対応する「が存在しない確率
    let mut prob = LazySegtree::<MulAdd>::new(N+3);
    for i in 0..N{
        prob.set(i,(Mint::new(1)/Mint::new(4))*(Mint::new(3)/Mint::new(4)).pow(i as u64));
    }
    for i in (1..N).rev(){
        prob.apply_range(0..rank[i],Mint::new(3)/Mint::new(4));
        prob.set(rank[i],Mint::new(0));
        prob.apply_range(rank[i]+1..N,Mint::new(4)/Mint::new(3));
        ans += Mint::new(Point[i].1-Point[i-1].1)*(Mint::new(1)-prob.prod(0..N)-(Mint::new(3)/Mint::new(4)).pow(i as u64))
    }
    
    ans *= Mint::new(4).pow(N as u64);
    ans *= Mint::new(2);
    println!("{}",ans);
}





//ac-library-rs
use std::ops::*;
use std::fmt;

#[derive(Copy, Clone, Eq, PartialEq, Default, Hash, Debug)]
pub struct ModInt998244353(u32);

impl ModInt998244353 {
    pub const MOD: u32 = 998_244_353;

    pub fn new<T: Into<i128>>(v: T) -> Self {
        let m = Self::MOD as i128;
        let mut x = v.into() % m;
        if x < 0 {
            x += m;
        }
        Self(x as u32)
    }

    pub fn raw(v: u32) -> Self {
        debug_assert!(v < Self::MOD);
        Self(v)
    }

    pub fn val(self) -> u32 {
        self.0
    }

    pub fn pow(self, mut e: u64) -> Self {
        let mut base = self;
        let mut res = Self::raw(1);
        while e > 0 {
            if e & 1 == 1 {
                res *= base;
            }
            base *= base;
            e >>= 1;
        }
        res
    }

    pub fn inv(self) -> Self {
        self.pow((Self::MOD - 2) as u64)
    }
}

impl From<i8> for ModInt998244353 { fn from(v: i8) -> Self { Self::new(v) } }
impl From<i16> for ModInt998244353 { fn from(v: i16) -> Self { Self::new(v) } }
impl From<i32> for ModInt998244353 { fn from(v: i32) -> Self { Self::new(v) } }
impl From<i64> for ModInt998244353 { fn from(v: i64) -> Self { Self::new(v) } }
impl From<u8> for ModInt998244353 { fn from(v: u8) -> Self { Self::new(v) } }
impl From<u16> for ModInt998244353 { fn from(v: u16) -> Self { Self::new(v) } }
impl From<u32> for ModInt998244353 { fn from(v: u32) -> Self { Self::new(v) } }
impl From<u64> for ModInt998244353 { fn from(v: u64) -> Self { Self::new(v) } }
impl From<usize> for ModInt998244353 { fn from(v: usize) -> Self { Self::new(v as i128) } }

impl fmt::Display for ModInt998244353 {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.0)
    }
}

impl Add for ModInt998244353 {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        let mut x = self.0 + rhs.0;
        if x >= Self::MOD {
            x -= Self::MOD;
        }
        Self(x)
    }
}

impl AddAssign for ModInt998244353 {
    fn add_assign(&mut self, rhs: Self) {
        *self = *self + rhs;
    }
}

impl Sub for ModInt998244353 {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        let mut x = self.0.wrapping_sub(rhs.0);
        if x >= Self::MOD {
            x = x.wrapping_add(Self::MOD);
        }
        Self(x)
    }
}

impl SubAssign for ModInt998244353 {
    fn sub_assign(&mut self, rhs: Self) {
        *self = *self - rhs;
    }
}

impl Mul for ModInt998244353 {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self {
        Self(((self.0 as u64 * rhs.0 as u64) % Self::MOD as u64) as u32)
    }
}

impl MulAssign for ModInt998244353 {
    fn mul_assign(&mut self, rhs: Self) {
        *self = *self * rhs;
    }
}

impl Div for ModInt998244353 {
    type Output = Self;
    fn div(self, rhs: Self) -> Self {
        self * rhs.inv()
    }
}

impl DivAssign for ModInt998244353 {
    fn div_assign(&mut self, rhs: Self) {
        *self = *self / rhs;
    }
}

impl Neg for ModInt998244353 {
    type Output = Self;
    fn neg(self) -> Self {
        if self.0 == 0 { self } else { Self(Self::MOD - self.0) }
    }
}

pub trait Monoid {
    type S: Clone;

    fn identity() -> Self::S;
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S;
}

fn ceil_pow2(n: usize) -> usize {
    let mut x = 0usize;
    while (1usize << x) < n {
        x += 1;
    }
    x
}

pub trait MapMonoid {
    type M: Monoid;
    type F: Clone;

    fn identity_element() -> <Self::M as Monoid>::S {
        Self::M::identity()
    }

    fn binary_operation(
        a: &<Self::M as Monoid>::S,
        b: &<Self::M as Monoid>::S,
    ) -> <Self::M as Monoid>::S {
        Self::M::binary_operation(a, b)
    }

    fn identity_map() -> Self::F;
    fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S;
    fn composition(f: &Self::F, g: &Self::F) -> Self::F;
}

#[derive(Clone)]
pub struct LazySegtree<F: MapMonoid> {
    n: usize,
    size: usize,
    log: usize,
    d: Vec<<F::M as Monoid>::S>,
    lz: Vec<F::F>,
}

impl<F: MapMonoid> Default for LazySegtree<F> {
    fn default() -> Self {
        Self::new(0)
    }
}

impl<F: MapMonoid> LazySegtree<F> {
    pub fn new(n: usize) -> Self {
        vec![F::identity_element(); n].into()
    }

    pub fn len(&self) -> usize {
        self.n
    }

    pub fn is_empty(&self) -> bool {
        self.n == 0
    }

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

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

    pub fn prod<R>(&mut self, range: R) -> <F::M as Monoid>::S
    where
        R: RangeBounds<usize>,
    {
        if range.start_bound() == Bound::Unbounded && range.end_bound() == Bound::Unbounded {
            return self.all_prod();
        }

        let mut r = match range.end_bound() {
            Bound::Included(r) => *r + 1,
            Bound::Excluded(r) => *r,
            Bound::Unbounded => self.n,
        };

        let mut l = match range.start_bound() {
            Bound::Included(l) => *l,
            Bound::Excluded(l) => *l + 1,
            Bound::Unbounded => 0,
        };

        assert!(l <= r && r <= self.n);
        if l == r {
            return F::identity_element();
        }

        l += self.size;
        r += self.size;

        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 mut sml = F::identity_element();
        let mut smr = F::identity_element();

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

        F::binary_operation(&sml, &smr)
    }

    pub fn all_prod(&self) -> <F::M as Monoid>::S {
        self.d[1].clone()
    }

    pub fn apply(&mut self, mut p: usize, f: F::F) {
        assert!(p < self.n);
        p += self.size;
        for i in (1..=self.log).rev() {
            self.push(p >> i);
        }
        self.d[p] = F::mapping(&f, &self.d[p]);
        for i in 1..=self.log {
            self.update(p >> i);
        }
    }

    pub fn apply_range<R>(&mut self, range: R, f: F::F)
    where
        R: RangeBounds<usize>,
    {
        let mut r = match range.end_bound() {
            Bound::Included(r) => *r + 1,
            Bound::Excluded(r) => *r,
            Bound::Unbounded => self.n,
        };

        let mut l = match range.start_bound() {
            Bound::Included(l) => *l,
            Bound::Excluded(l) => *l + 1,
            Bound::Unbounded => 0,
        };

        assert!(l <= r && r <= self.n);
        if l == r {
            return;
        }

        l += self.size;
        r += self.size;

        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 l2 = l;
        let r2 = r;

        while l < r {
            if l & 1 != 0 {
                self.all_apply(l, f.clone());
                l += 1;
            }
            if r & 1 != 0 {
                r -= 1;
                self.all_apply(r, f.clone());
            }
            l >>= 1;
            r >>= 1;
        }

        l = l2;
        r = r2;

        for i in 1..=self.log {
            if ((l >> i) << i) != l {
                self.update(l >> i);
            }
            if ((r >> i) << i) != r {
                self.update((r - 1) >> i);
            }
        }
    }

    pub fn max_right<G>(&mut self, mut l: usize, g: G) -> usize
    where
        G: Fn(<F::M as Monoid>::S) -> bool,
    {
        assert!(l <= self.n);
        assert!(g(F::identity_element()));
        if l == self.n {
            return self.n;
        }

        l += self.size;
        for i in (1..=self.log).rev() {
            self.push(l >> i);
        }

        let mut sm = F::identity_element();

        loop {
            while l % 2 == 0 {
                l >>= 1;
            }
            let nxt = F::binary_operation(&sm, &self.d[l]);
            if !g(nxt.clone()) {
                while l < self.size {
                    self.push(l);
                    l *= 2;
                    let nxt = F::binary_operation(&sm, &self.d[l]);
                    if g(nxt.clone()) {
                        sm = nxt;
                        l += 1;
                    }
                }
                return l - self.size;
            }
            sm = nxt;
            l += 1;
            if l & l.wrapping_neg() == l {
                break;
            }
        }

        self.n
    }

    pub fn min_left<G>(&mut self, mut r: usize, g: G) -> usize
    where
        G: Fn(<F::M as Monoid>::S) -> bool,
    {
        assert!(r <= self.n);
        assert!(g(F::identity_element()));
        if r == 0 {
            return 0;
        }

        r += self.size;
        for i in (1..=self.log).rev() {
            self.push((r - 1) >> i);
        }

        let mut sm = F::identity_element();

        loop {
            r -= 1;
            while r > 1 && r % 2 == 1 {
                r >>= 1;
            }
            let nxt = F::binary_operation(&self.d[r], &sm);
            if !g(nxt.clone()) {
                while r < self.size {
                    self.push(r);
                    r = 2 * r + 1;
                    let nxt = F::binary_operation(&self.d[r], &sm);
                    if g(nxt.clone()) {
                        sm = nxt;
                        r -= 1;
                    }
                }
                return r + 1 - self.size;
            }
            sm = nxt;
            if r & r.wrapping_neg() == r {
                break;
            }
        }

        0
    }

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

    fn all_apply(&mut self, k: usize, f: F::F) {
        self.d[k] = F::mapping(&f, &self.d[k]);
        if k < self.size {
            self.lz[k] = F::composition(&f, &self.lz[k]);
        }
    }

    fn push(&mut self, k: usize) {
        let f = self.lz[k].clone();
        self.all_apply(2 * k, f.clone());
        self.all_apply(2 * k + 1, f);
        self.lz[k] = F::identity_map();
    }
}

impl<F: MapMonoid> From<Vec<<F::M as Monoid>::S>> for LazySegtree<F> {
    fn from(v: Vec<<F::M as Monoid>::S>) -> Self {
        let n = v.len();
        let log = ceil_pow2(n);
        let size = 1 << log;
        let mut d = vec![F::identity_element(); 2 * size];
        let lz = vec![F::identity_map(); size];

        d[size..(size + n)].clone_from_slice(&v);

        let mut ret = Self { n, size, log, d, lz };
        for i in (1..size).rev() {
            ret.update(i);
        }
        ret
    }
}