結果
| 問題 |
No.3327 うるせぇ、ポリオミノぶつけんぞ
|
| コンテスト | |
| ユーザー |
 elphe
|
| 提出日時 | 2025-11-15 12:27:43 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 78 ms / 3,000 ms |
| コード長 | 7,860 bytes |
| コンパイル時間 | 13,989 ms |
| コンパイル使用メモリ | 396,984 KB |
| 実行使用メモリ | 18,476 KB |
| 最終ジャッジ日時 | 2025-11-15 12:28:03 |
| 合計ジャッジ時間 | 16,462 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 24 |
ソースコード
use proconio::{fastout, input};
#[allow(unused)]
mod mylib {
pub struct SegmentTree<S: Monoid> {
container: Vec<Vec<S::T>>,
}
pub trait Monoid {
type T: Clone;
const DEFAULT: Self::T;
fn op(a: &Self::T, b: &Self::T) -> Self::T;
}
impl<S: Monoid> SegmentTree<S> {
pub fn update(&mut self, index: usize, value: S::T) {
self.container[0][index] = value;
for layer in 1..self.container.len() {
self.container[layer][index >> layer] = S::op(
&self.container[layer - 1][(index >> layer) << 1],
&self.container[layer - 1][((index >> layer) << 1) | 1],
);
}
}
pub fn range_pick_up(&self, mut l: usize, mut r: usize) -> S::T {
let mut ans_l = S::DEFAULT;
let mut ans_r = S::DEFAULT;
for layer in 0..self.container.len() {
if l >= r {
break;
}
if ((l >> layer) & 1) == 1 {
ans_l = S::op(&ans_l, &self.container[layer][l >> layer]);
l += 1 << layer;
}
if ((r >> layer) & 1) == 1 {
ans_r = S::op(&self.container[layer][(r >> layer) - 1], &ans_r);
r -= 1 << layer;
}
}
S::op(&ans_l, &ans_r)
}
}
impl<S: Monoid> From<Vec<S::T>> for SegmentTree<S> {
fn from(mut value: Vec<S::T>) -> Self {
let mut st = Self {
container: Vec::<Vec<S::T>>::new(),
};
if value.is_empty() {
return st;
}
let mut len: usize = 1;
while len < value.len() {
len *= 2;
}
value.extend(vec![S::DEFAULT; len - value.len()]);
st.container.push(value);
let len = len;
let mut layer: usize = 1;
while (len >> layer) > 0 {
st.container.push(vec![S::DEFAULT; len]);
for i in 0..(len >> layer) {
st.container[layer][i] = S::op(
&st.container[layer - 1][i << 1],
&st.container[layer - 1][(i << 1) | 1],
);
}
layer += 1;
}
st
}
}
impl<S: Monoid> std::ops::Index<usize> for SegmentTree<S> {
type Output = S::T;
fn index(&self, index: usize) -> &Self::Output {
&self.container[0][index]
}
}
pub struct MaxSegmentTree<S: Monoid>
where
S::T: Clone + PartialOrd,
{
st: SegmentTree<S>,
}
impl<S: Monoid> MaxSegmentTree<S>
where
S::T: PartialOrd,
{
pub fn update(&mut self, index: usize, value: S::T) {
self.st.update(index, value)
}
pub fn range_pick_up(&self, l: usize, r: usize) -> S::T {
self.st.range_pick_up(l, r)
}
pub fn leftest_above(&self, border: S::T, mut l: usize, mut r: usize) -> Option<usize> {
if l >= r || self.st.container.is_empty() {
return None;
}
let mut layer = 0;
let mut candidate_layer = usize::MAX;
let mut candidate_index = usize::MAX;
while layer < self.st.container.len() {
if (l & 1) == 1 {
if self.st.container[layer][l] >= border {
candidate_layer = layer;
candidate_index = l;
break;
}
l += 1;
}
if (r & 1) == 1 {
if self.st.container[layer][r - 1] >= border {
candidate_layer = layer;
candidate_index = r - 1;
}
// r -= 1;
}
layer += 1;
l >>= 1;
r >>= 1;
}
if candidate_layer == usize::MAX {
return None;
}
while candidate_layer > 0 {
if self.st.container[candidate_layer - 1][candidate_index << 1] >= border {
candidate_index <<= 1;
} else {
candidate_index = (candidate_index << 1) | 1;
}
candidate_layer -= 1;
}
Some(candidate_index)
}
pub fn rightest_above(&self, border: S::T, mut l: usize, mut r: usize) -> Option<usize> {
if l >= r || self.st.container.is_empty() {
return None;
}
let mut layer = 0;
let mut candidate_layer = usize::MAX;
let mut candidate_index = usize::MAX;
while layer < self.st.container.len() {
if (r & 1) == 1 {
if self.st.container[layer][r - 1] >= border {
candidate_layer = layer;
candidate_index = r - 1;
break;
}
// r -= 1;
}
if (l & 1) == 1 {
if self.st.container[layer][l] >= border {
candidate_layer = layer;
candidate_index = l;
}
l += 1;
}
layer += 1;
l >>= 1;
r >>= 1;
}
if candidate_layer == usize::MAX {
return None;
}
while candidate_layer > 0 {
if self.st.container[candidate_layer - 1][(candidate_index << 1) | 1] >= border {
candidate_index = (candidate_index << 1) | 1;
} else {
candidate_index <<= 1;
}
candidate_layer -= 1;
}
Some(candidate_index)
}
}
impl<S: Monoid> From<Vec<S::T>> for MaxSegmentTree<S>
where
S::T: PartialOrd,
{
fn from(value: Vec<S::T>) -> Self {
Self {
st: SegmentTree::<S>::from(value),
}
}
}
impl<S: Monoid> std::ops::Index<usize> for MaxSegmentTree<S>
where
S::T: PartialOrd,
{
type Output = S::T;
fn index(&self, index: usize) -> &Self::Output {
&self.st[index]
}
}
}
struct S {}
impl mylib::Monoid for S {
type T = u32;
const DEFAULT: Self::T = u32::MIN;
fn op(a: &Self::T, b: &Self::T) -> Self::T {
*a.max(&b)
}
}
#[fastout]
fn main() {
input! {
n: usize,
q: usize,
a: [u32; n],
queries: [(u8, u32); q],
}
println!("{}", output(solve(n, q, a, queries)));
}
fn solve(n: usize, q: usize, a: Vec<u32>, queries: Vec<(u8, u32)>) -> Vec<i32> {
let mut niwaka = mylib::MaxSegmentTree::<S>::from(a);
let mut ans = Vec::with_capacity(q);
for (c, x) in queries {
match c {
1 => match niwaka.leftest_above(x + 1, 0, n) {
Some(pos) => {
niwaka.update(pos, 0);
ans.push((pos + 1) as i32);
}
None => ans.push(-1),
},
2 => match niwaka.rightest_above(x + 1, 0, n) {
Some(pos) => {
niwaka.update(pos, 0);
ans.push((pos + 1) as i32);
}
None => ans.push(-1),
},
_ => (),
}
}
ans
}
fn output(ans: Vec<i32>) -> String {
ans.into_iter()
.map(|x| x.to_string())
.collect::<Vec<_>>()
.join("\n")
}