結果
| 問題 |
No.1675 Strange Minimum Query
|
| コンテスト | |
| ユーザー |
 manta1130
|
| 提出日時 | 2021-09-10 22:31:31 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 17,849 bytes |
| コンパイル時間 | 13,627 ms |
| コンパイル使用メモリ | 399,716 KB |
| 実行使用メモリ | 15,248 KB |
| 最終ジャッジ日時 | 2024-06-12 01:23:17 |
| 合計ジャッジ時間 | 26,031 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 14 WA * 20 |
コンパイルメッセージ
warning: unused imports: `BTreeMap`, `BinaryHeap`
--> src/main.rs:4:24
|
4 | use std::collections::{BTreeMap, BinaryHeap};
| ^^^^^^^^ ^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
ソースコード
#[allow(unused_imports)]
use std::io::{stdout, BufWriter, Write};
use std::collections::{BTreeMap, BinaryHeap};
fn main() {
let out = stdout();
let mut out = BufWriter::new(out.lock());
inputv! {
n:usize,q:usize
}
let mut query = vec![];
let mut max = 0;
for _ in 0..q {
inputv! {
l:usize,r:usize,b:u64
}
max = std::cmp::max(max, b);
query.push((l - 1, r, b));
}
let qc = query.clone();
query.sort_by_key(|q| std::cmp::Reverse(q.2));
let mut ans = vec![max; n];
let mut mex = Mex::new();
for (l, r, b) in query {
let idx = mex.mex(l as i64, r as i64).unwrap_or(l as i64);
ans[idx as usize] = b;
mex.insert_range(l as i64, r as i64);
}
let sg: Segtree<Min<_>> = ans.clone().into();
let mut flag = true;
for (l, r, b) in qc {
if sg.prod(l, r) != b {
flag = false;
break;
}
}
//dbg!(&ans);
if !flag {
writeln!(out, "-1").unwrap();
} else {
for i in 0..n {
if i == n - 1 {
writeln!(out, "{}", ans[i]).unwrap();
} else {
write!(out, "{} ", ans[i]).unwrap();
}
}
}
}
//https://github.com/rust-lang-ja/ac-library-rs
//https://github.com/manta1130/competitive-template-rs
use input::*;
use mex::*;
use segtree::*;
pub mod input {
use std::cell::RefCell;
use std::io;
pub const SPLIT_DELIMITER: char = ' ';
pub use std::io::prelude::*;
thread_local! {
pub static INPUT_BUFFER:RefCell<std::collections::VecDeque<String>>=RefCell::new(std::collections::VecDeque::new());
}
#[macro_export]
macro_rules! input_internal {
($x:ident : $t:ty) => {
INPUT_BUFFER.with(|p| {
if p.borrow().len() == 0 {
let temp_str = input_line_str();
let mut split_result_iter = temp_str
.split(SPLIT_DELIMITER)
.map(|q| q.to_string())
.collect::<std::collections::VecDeque<_>>();
p.borrow_mut().append(&mut split_result_iter)
}
});
let mut buf_split_result = String::new();
INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap());
let $x: $t = buf_split_result.parse().unwrap();
};
(mut $x:ident : $t:ty) => {
INPUT_BUFFER.with(|p| {
if p.borrow().len() == 0 {
let temp_str = input_line_str();
let mut split_result_iter = temp_str
.split(SPLIT_DELIMITER)
.map(|q| q.to_string())
.collect::<std::collections::VecDeque<_>>();
p.borrow_mut().append(&mut split_result_iter)
}
});
let mut buf_split_result = String::new();
INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap());
let mut $x: $t = buf_split_result.parse().unwrap();
};
}
pub fn input_buffer_is_empty() -> bool {
let mut empty = false;
INPUT_BUFFER.with(|p| {
if p.borrow().len() == 0 {
empty = true;
}
});
empty
}
#[macro_export]
macro_rules! inputv {
($i:ident : $t:ty) => {
input_internal!{$i : $t}
};
(mut $i:ident : $t:ty) => {
input_internal!{mut $i : $t}
};
($i:ident : $t:ty $(,)*) => {
input_internal!{$i : $t}
};
(mut $i:ident : $t:ty $(,)*) => {
input_internal!{mut $i : $t}
};
(mut $i:ident : $t:ty,$($q:tt)*) => {
input_internal!{mut $i : $t}
inputv!{$($q)*}
};
($i:ident : $t:ty,$($q:tt)*) => {
input_internal!{$i : $t}
inputv!{$($q)*}
};
}
pub fn input_all() {
INPUT_BUFFER.with(|p| {
if p.borrow().len() == 0 {
let mut temp_str = String::new();
std::io::stdin().read_to_string(&mut temp_str).unwrap();
let mut split_result_iter = temp_str
.split_whitespace()
.map(|q| q.to_string())
.collect::<std::collections::VecDeque<_>>();
p.borrow_mut().append(&mut split_result_iter)
}
});
}
pub fn input_line_str() -> String {
let mut s = String::new();
io::stdin().read_line(&mut s).unwrap();
s.trim().to_string()
}
#[allow(clippy::match_wild_err_arm)]
pub fn input_vector<T>() -> Vec<T>
where
T: std::str::FromStr,
{
let mut v: Vec<T> = Vec::new();
let s = input_line_str();
let split_result = s.split(SPLIT_DELIMITER);
for z in split_result {
let buf = match z.parse() {
Ok(r) => r,
Err(_) => panic!("Parse Error",),
};
v.push(buf);
}
v
}
#[allow(clippy::match_wild_err_arm)]
pub fn input_vector_row<T>(n: usize) -> Vec<T>
where
T: std::str::FromStr,
{
let mut v = Vec::with_capacity(n);
for _ in 0..n {
let buf = match input_line_str().parse() {
Ok(r) => r,
Err(_) => panic!("Parse Error",),
};
v.push(buf);
}
v
}
pub trait ToCharVec {
fn to_charvec(&self) -> Vec<char>;
}
impl ToCharVec for String {
fn to_charvec(&self) -> Vec<char> {
self.to_string().chars().collect::<Vec<_>>()
}
}
}
pub mod internal_bit {
#[allow(dead_code)]
pub(crate) fn ceil_pow2(n: u32) -> u32 {
32 - n.saturating_sub(1).leading_zeros()
}
}
pub mod internal_type_traits {
use std::{
fmt,
iter::{Product, Sum},
ops::{
Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Div,
DivAssign, Mul, MulAssign, Not, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub,
SubAssign,
},
};
pub trait Integral:
'static
+ Send
+ Sync
+ Copy
+ Ord
+ Not<Output = Self>
+ Add<Output = Self>
+ Sub<Output = Self>
+ Mul<Output = Self>
+ Div<Output = Self>
+ Rem<Output = Self>
+ AddAssign
+ SubAssign
+ MulAssign
+ DivAssign
+ RemAssign
+ Sum
+ Product
+ BitOr<Output = Self>
+ BitAnd<Output = Self>
+ BitXor<Output = Self>
+ BitOrAssign
+ BitAndAssign
+ BitXorAssign
+ Shl<Output = Self>
+ Shr<Output = Self>
+ ShlAssign
+ ShrAssign
+ fmt::Display
+ fmt::Debug
+ fmt::Binary
+ fmt::Octal
+ Zero
+ One
+ BoundedBelow
+ BoundedAbove
{
}
pub trait Zero {
fn zero() -> Self;
}
pub trait One {
fn one() -> Self;
}
pub trait BoundedBelow {
fn min_value() -> Self;
}
pub trait BoundedAbove {
fn max_value() -> Self;
}
macro_rules! impl_integral {
($($ty:ty),*) => {
$(
impl Zero for $ty {
#[inline]
fn zero() -> Self {
0
}
}
impl One for $ty {
#[inline]
fn one() -> Self {
1
}
}
impl BoundedBelow for $ty {
#[inline]
fn min_value() -> Self {
Self::min_value()
}
}
impl BoundedAbove for $ty {
#[inline]
fn max_value() -> Self {
Self::max_value()
}
}
impl Integral for $ty {}
)*
};
}
impl_integral!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize);
}
pub mod mex {
use std::collections::BTreeSet;
type ValueType = i64;
pub struct Mex {
set: BTreeSet<(ValueType, ValueType)>,
}
impl Default for Mex {
fn default() -> Self {
Self::new()
}
}
impl Mex {
pub fn new() -> Self {
let mut set = BTreeSet::new();
set.insert((ValueType::min_value(), ValueType::min_value()));
set.insert((ValueType::max_value(), ValueType::max_value()));
Mex { set }
}
pub fn insert(&mut self, x: ValueType) {
let back = *self
.set
.range(..(x, ValueType::max_value()))
.next_back()
.unwrap();
let next = *self
.set
.range((x + 1, ValueType::min_value())..)
.next()
.unwrap();
if back.1 == x && x + 1 == next.0 {
self.set.remove(&back);
self.set.remove(&next);
self.set.insert((back.0, next.1));
} else if back.1 == x {
self.set.remove(&back);
self.set.insert((back.0, x + 1));
} else if x + 1 == next.0 {
self.set.remove(&next);
self.set.insert((x, next.1));
} else {
self.set.insert((x, x + 1));
}
}
pub fn insert_range(&mut self, f: i64, t: i64) {
let left = self.mex(f - 1, f).is_some();
let right = self.mex(t, t + 1).is_some();
self.remove(f - 1);
self.remove(t);
self.remove_range(f, t);
self.set.insert((f, t));
if left {
self.insert(f - 1);
}
if right {
self.insert(t);
}
}
pub fn remove_range(&mut self, f: i64, t: i64) {
let left = self.mex(f - 1, f).is_some();
let right = self.mex(t, t + 1).is_some();
self.insert(f);
self.insert(t - 1);
self.remove(f - 1);
self.remove(t);
let remove_list = self
.set
.range((f, f)..=(t - 1, t))
.cloned()
.collect::<Vec<_>>();
for k in remove_list {
self.set.remove(&k);
}
if left {
self.insert(f - 1);
}
if right {
self.insert(t);
}
}
pub fn remove(&mut self, x: ValueType) {
let back = *self
.set
.range(..(x, ValueType::max_value()))
.next_back()
.unwrap();
if back.1 > x {
self.set.remove(&back);
self.set.insert((back.0, x));
self.set.insert((x + 1, back.1));
}
}
pub fn mex(&mut self, f: ValueType, t: ValueType) -> Option<ValueType> {
if f >= t {
return None;
}
let r = self
.set
.range(..(f, ValueType::max_value()))
.next_back()
.unwrap()
.1;
if r >= t {
None
} else {
Some(std::cmp::max(r, f))
}
}
}
}
pub mod segtree {
use crate::internal_bit::ceil_pow2;
use crate::internal_type_traits::{BoundedAbove, BoundedBelow, One, Zero};
use std::cmp::{max, min};
use std::convert::Infallible;
use std::marker::PhantomData;
use std::ops::{Add, Mul};
pub trait Monoid {
type S: Clone;
fn identity() -> Self::S;
fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S;
}
pub struct Max<S>(Infallible, PhantomData<fn() -> S>);
impl<S> Monoid for Max<S>
where
S: Copy + Ord + BoundedBelow,
{
type S = S;
fn identity() -> Self::S {
S::min_value()
}
fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
max(*a, *b)
}
}
pub struct Min<S>(Infallible, PhantomData<fn() -> S>);
impl<S> Monoid for Min<S>
where
S: Copy + Ord + BoundedAbove,
{
type S = S;
fn identity() -> Self::S {
S::max_value()
}
fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
min(*a, *b)
}
}
pub struct Additive<S>(Infallible, PhantomData<fn() -> S>);
impl<S> Monoid for Additive<S>
where
S: Copy + Add<Output = S> + Zero,
{
type S = S;
fn identity() -> Self::S {
S::zero()
}
fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
*a + *b
}
}
pub struct Multiplicative<S>(Infallible, PhantomData<fn() -> S>);
impl<S> Monoid for Multiplicative<S>
where
S: Copy + Mul<Output = S> + One,
{
type S = S;
fn identity() -> Self::S {
S::one()
}
fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
*a * *b
}
}
impl<M: Monoid> Default for Segtree<M> {
fn default() -> Self {
Segtree::new(0)
}
}
impl<M: Monoid> Segtree<M> {
pub fn new(n: usize) -> Segtree<M> {
vec![M::identity(); n].into()
}
}
impl<M: Monoid> From<Vec<M::S>> for Segtree<M> {
fn from(v: Vec<M::S>) -> Self {
let n = v.len();
let log = ceil_pow2(n as u32) as usize;
let size = 1 << log;
let mut d = vec![M::identity(); 2 * size];
d[size..(size + n)].clone_from_slice(&v);
let mut ret = Segtree { n, size, log, d };
for i in (1..size).rev() {
ret.update(i);
}
ret
}
}
impl<M: Monoid> Segtree<M> {
pub fn set(&mut self, mut p: usize, x: M::S) {
assert!(p < self.n);
p += self.size;
self.d[p] = x;
for i in 1..=self.log {
self.update(p >> i);
}
}
pub fn get(&self, p: usize) -> M::S {
assert!(p < self.n);
self.d[p + self.size].clone()
}
pub fn prod(&self, mut l: usize, mut r: usize) -> M::S {
assert!(l <= r && r <= self.n);
let mut sml = M::identity();
let mut smr = M::identity();
l += self.size;
r += self.size;
while l < r {
if l & 1 != 0 {
sml = M::binary_operation(&sml, &self.d[l]);
l += 1;
}
if r & 1 != 0 {
r -= 1;
smr = M::binary_operation(&self.d[r], &smr);
}
l >>= 1;
r >>= 1;
}
M::binary_operation(&sml, &smr)
}
pub fn all_prod(&self) -> M::S {
self.d[1].clone()
}
pub fn max_right<F>(&self, mut l: usize, f: F) -> usize
where
F: Fn(&M::S) -> bool,
{
assert!(l <= self.n);
assert!(f(&M::identity()));
if l == self.n {
return self.n;
}
l += self.size;
let mut sm = M::identity();
while {
while l % 2 == 0 {
l >>= 1;
}
if !f(&M::binary_operation(&sm, &self.d[l])) {
while l < self.size {
l *= 2;
let res = M::binary_operation(&sm, &self.d[l]);
if f(&res) {
sm = res;
l += 1;
}
}
return l - self.size;
}
sm = M::binary_operation(&sm, &self.d[l]);
l += 1;
{
let l = l as isize;
(l & -l) != l
}
} {}
self.n
}
pub fn min_left<F>(&self, mut r: usize, f: F) -> usize
where
F: Fn(&M::S) -> bool,
{
assert!(r <= self.n);
assert!(f(&M::identity()));
if r == 0 {
return 0;
}
r += self.size;
let mut sm = M::identity();
while {
r -= 1;
while r > 1 && r % 2 == 1 {
r >>= 1;
}
if !f(&M::binary_operation(&self.d[r], &sm)) {
while r < self.size {
r = 2 * r + 1;
let res = M::binary_operation(&self.d[r], &sm);
if f(&res) {
sm = res;
r -= 1;
}
}
return r + 1 - self.size;
}
sm = M::binary_operation(&self.d[r], &sm);
{
let r = r as isize;
(r & -r) != r
}
} {}
0
}
fn update(&mut self, k: usize) {
self.d[k] = M::binary_operation(&self.d[2 * k], &self.d[2 * k + 1]);
}
}
pub struct Segtree<M>
where
M: Monoid,
{
n: usize,
size: usize,
log: usize,
d: Vec<M::S>,
}
}