結果
| 問題 |
No.3122 Median of Medians of Division
|
| コンテスト | |
| ユーザー |
 rhoo
|
| 提出日時 | 2025-04-19 13:19:54 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,294 bytes |
| コンパイル時間 | 13,777 ms |
| コンパイル使用メモリ | 399,168 KB |
| 実行使用メモリ | 32,648 KB |
| 最終ジャッジ日時 | 2025-04-19 13:20:13 |
| 合計ジャッジ時間 | 15,824 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | RE * 1 |
| other | RE * 40 |
コンパイルメッセージ
warning: unreachable statement --> src/main.rs:78:5 | 76 | panic!(); | -------- any code following this expression is unreachable 77 | 78 | let mut seq=R::new(0,seq_ps); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ unreachable statement | = note: `#[warn(unreachable_code)]` on by default
ソースコード
#![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,
a:[usize;n],
}
let mut qs=vec![];
for _ in 0..q{
input!{
t:usize,
}
if t==1{
// change
input!{
i:Usize1,
x:usize,
}
let new=Q{
t:Change,i,x,
l:!0,r:!0,
};
qs.push(new);
} else{
// get
input!{
l:Usize1,
r:usize,
}
let new=Q{
t:Get,i:!0,x:!0,
l,r,
};
qs.push(new);
}
}
let mut seq_ps=vec![];
let mut adj_ps=vec![];
{
let mut a=a.clone();
for i in 0..n{
seq_ps.push((i,a[i]));
if 1<=i{
adj_ps.push((i-1,a[i-1].max(a[i])));
}
}
for &q in &qs{
if q.t!=Change{
continue;
}
a[q.i]=q.x;
seq_ps.push((q.i,q.x));
if 1<=q.i{
adj_ps.push((q.i-1,a[q.i-1].max(a[q.i])));
}
if q.i+1<a.len(){
adj_ps.push((q.i,a[q.i].max(a[q.i+1])));
}
}
}
panic!();
let mut seq=R::new(0,seq_ps);
let mut adj=R::new(0,adj_ps);
let mut a=a;
let get=|re:&R,l:usize,r:usize,a:usize|->i64{
assert!(0<=a as i64);
let right=if (r as i64)<0{
0
} else{
re.find(r,a)
};
let left=if (l as i64)<0{
0
} else{
re.find(l,a)
};
assert!(left<=right);
right-left
};
for i in 0..n{
seq.add(i,a[i],1);
if 1<=i{
adj.add(i-1,a[i-1].max(a[i]),1);
}
}
for &q in &qs{
if q.t==Change{
let i=q.i;
let x=q.x;
seq.add(i,a[i],-1);
seq.add(i,x,1);
if 1<=i{
adj.add(i-1,a[i-1].max(a[i]),-1);
adj.add(i-1,a[i-1].max(x),1);
}
if i+1<a.len(){
adj.add(i,a[i].max(a[i+1]),-1);
adj.add(i,x.max(a[i+1]),1);
}
a[i]=x;
} else{
let l=q.l;
let r=q.r;
let mut ok=0;
let mut ng=1e9 as usize+1;
// eprintln!("Query: {:?}",&a[l..r]);
while ng-ok>1{
let m=(ok+ng)/2;
let z=get(&adj,l-1,r-2,m-1); // [l,r)で隣接する２つがどっちもm未満である場所の数
// assert!(z==verify_z(&a[l..r],m));
let y=get(&seq,l-1,r-1,m-1); // [l,r)でm未満の場所の数
// assert!(y==verify_y(&a[l..r],m));
let x=y-z; // // [l,r)でk未満の連続部分列の個数
// eprintln!("{m} : {} {} {}",x,y,z);
if x as usize<=(r-l-y as usize+x as usize-1)/2{
ok=m;
} else{
ng=m;
}
}
// eprintln!();
println!("{ok}");
}
}
}
fn verify_z(a:&[usize],m:usize)->i64{
let mut ret=0;
for i in 1..a.len(){
ret+=(a[i-1].max(a[i])<m) as i64;
}
ret
}
fn verify_y(a:&[usize],m:usize)->i64{
let mut ret=0;
for i in 0..a.len(){
ret+=(a[i]<m) as i64;
}
ret
}
#[derive(Clone,Copy,PartialEq,Eq)]
enum T{
Change,Get,
}
use T::*;
#[derive(Clone,Copy)]
struct Q{
t:T,
i:usize,
x:usize,
l:usize,
r:usize,
}
type R=RectangleSum<usize,i64>;
// 窃盗：https://judge.yosupo.jp/submission/33203
// ありがとうございます...
struct RectangleSum<Index, Weight> {
point: Vec<(Index, Index)>,
row: Vec<Index>,
col: Vec<Vec<Index>>,
bit: Vec<Vec<Weight>>,
zero: Weight,
}
impl<Index, Weight> RectangleSum<Index, Weight>
where
Index: Ord + Copy,
Weight: std::ops::Add<Output = Weight> + Copy,
{
fn new(zero: Weight, point: Vec<(Index, Index)>) -> Self {
let mut r=RectangleSum {
point,
row: vec![],
col: vec![],
bit: vec![],
zero: zero,
};
r.build();
r
}
fn build(&mut self) {
let mut row: Vec<_> = self.point.iter().map(|p| p.0).collect();
row.sort();
row.dedup();
let mut col = vec![vec![]; row.len() + 1];
for &(x, y) in self.point.iter() {
let mut k = row.binary_search(&x).unwrap() + 1;
while let Some(a) = col.get_mut(k) {
a.push(y);
k += k & (!k + 1);
}
}
let mut bit = vec![vec![]; row.len() + 1];
for (bit, col) in bit.iter_mut().zip(col.iter_mut()).skip(1) {
col.sort();
col.dedup();
bit.resize(col.len() + 1, self.zero);
}
self.row = row;
self.col = col;
self.bit = bit;
}
fn add(&mut self, x: Index, y: Index, w: Weight) {
let mut x = self.row.binary_search(&x).unwrap() + 1;
while let Some(bit) = self.bit.get_mut(x) {
let mut y = self.col[x].binary_search(&y).unwrap() + 1;
while let Some(v) = bit.get_mut(y) {
*v = *v + w;
y += y & (!y + 1);
}
x += x & (!x + 1);
}
}
// (-inf, x] * (-inf * y] の和
fn find(&self, x: Index, y: Index) -> Weight {
let upper_bound = |x: &[Index], v: &Index| -> usize {
use std::cmp::Ordering::Less;
x.binary_search_by(|p| p.cmp(v).then(Less)).unwrap_err()
};
let mut x = upper_bound(&self.row, &x);
let mut ans = self.zero;
while x > 0 {
let mut y = upper_bound(&self.col[x], &y);
let bit = &self.bit[x];
while y > 0 {
ans = ans + bit[y];
y -= y & (!y + 1);
}
x -= x & (!x + 1);
}
ans
}
}