結果
| 問題 |
No.877 Range ReLU Query
|
| コンテスト | |
| ユーザー |
 Haar
|
| 提出日時 | 2024-08-25 20:12:47 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1,053 ms / 2,000 ms |
| コード長 | 20,844 bytes |
| コンパイル時間 | 25,854 ms |
| コンパイル使用メモリ | 391,464 KB |
| 実行使用メモリ | 133,632 KB |
| 最終ジャッジ日時 | 2024-08-25 20:13:25 |
| 合計ジャッジ時間 | 24,412 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 20 |
コンパイルメッセージ
warning: unused imports: `utils::join_str::*`, `utils::transpose::*`
--> src/main.rs:8:34
|
8 | input, utils::fastio::*, utils::join_str::*, utils::transpose::*,
| ^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unused variable: `i`
--> src/main.rs:34:17
|
34 | for i in 0..q {
| ^ help: if this is intentional, prefix it with an underscore: `_i`
|
= note: `#[warn(unused_variables)]` on by default
ソースコード
// Bundled at 2024/08/25 20:08:40 +09:00
// Author: Haar
pub mod main {
use super::*;
use haar_lib::{
algebra::sum::*, algebra::tuple::*, algo::bsearch::*, ds::persistent_segtree::*, get,
input, utils::fastio::*, utils::join_str::*, utils::transpose::*,
};
#[allow(unused_imports)]
use std::cell::RefCell;
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet};
#[allow(unused_imports)]
use std::io::Write;
#[allow(unused_imports)]
use std::rc::Rc;
#[derive(Clone, Default)]
pub struct Problem {}
impl Problem {
pub fn main(&mut self) -> Result<(), Box<dyn std::error::Error>> {
let mut io = FastIO::new();
input!(io >> n: usize, q: usize, mut a: [u64; n]);
let m = Pair::new(Sum::<u64>::new(), Sum::<usize>::new());
let mut segs = vec![PersistenSegtree::new(n, m)];
let mut b = (0..n).map(|i| (a[i], i)).collect::<Vec<_>>();
b.sort();
b.reverse();
for (v, i) in b {
let s = segs.last().unwrap();
segs.push(s.assign(i, (v, 1)));
}
a.sort();
for i in 0..q {
input ! (io >> _t : usize , l : usize , r : usize , x : u64);
let j = n - lower_bound(&a, &x);
let (v, c) = segs[j].fold(l - 1..r);
let ans = v - x * c as u64;
io.writeln(ans);
}
Ok(())
}
}
}
fn main() {
main::Problem::default().main().unwrap();
}
use crate as haar_lib;
pub mod algebra {
pub mod traits {
pub trait AlgeStruct {
type Output;
}
pub trait BinaryOp: AlgeStruct {
fn op(&self, _: Self::Output, _: Self::Output) -> Self::Output;
}
pub trait Identity: AlgeStruct {
fn id(&self) -> Self::Output;
}
pub trait Inverse: AlgeStruct {
fn inv(&self, _: Self::Output) -> Self::Output;
}
pub trait Commutative {}
pub trait Associative {}
pub trait Idempotence {}
pub trait Semigroup: BinaryOp + Associative {}
impl<T: BinaryOp + Associative> Semigroup for T {}
pub trait Monoid: Semigroup + Identity {}
impl<T: Semigroup + Identity> Monoid for T {}
pub trait AbelianMonoid: Monoid + Commutative {}
impl<T: Monoid + Commutative> AbelianMonoid for T {}
pub trait Group: Monoid + Inverse {}
impl<T: Monoid + Inverse> Group for T {}
pub trait AbelianGroup: Group + Commutative {}
impl<T: Group + Commutative> AbelianGroup for T {}
pub trait Exponential<T: Clone>: BinaryOp<Output = T> + Identity {
fn exp(&self, mut a: Self::Output, mut n: u64) -> Self::Output {
let mut ret = self.id();
while n > 0 {
if n & 1 == 1 {
ret = self.op(ret, a.clone());
}
a = self.op(a.clone(), a);
n >>= 1;
}
ret
}
}
impl<T: Clone, A: BinaryOp<Output = T> + Identity> Exponential<T> for A {}
}
pub mod sum {
pub use crate::algebra::traits::*;
use crate::impl_algebra;
use std::marker::PhantomData;
#[derive(Clone, Copy, Default, Debug, PartialEq, Eq)]
pub struct Sum<T>(PhantomData<T>);
impl<T> Sum<T> {
pub fn new() -> Self {
Self(PhantomData)
}
}
impl<T> AlgeStruct for Sum<T> {
type Output = T;
}
impl_algebra!(Sum<i8>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: i8| -a, commu: {}, assoc: {});
impl_algebra!(Sum<i16>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: i16| -a, commu: {}, assoc: {});
impl_algebra!(Sum<i32>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: i32| -a, commu: {}, assoc: {});
impl_algebra!(Sum<i64>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: i64| -a, commu: {}, assoc: {});
impl_algebra!(Sum<i128>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: i128| -a, commu: {}, assoc: {});
impl_algebra!(Sum<isize>, op: |_, a, b| a + b, id: |_| 0, inv: |_, a: isize| -a, commu: {}, assoc: {});
impl_algebra!(Sum<u8>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
impl_algebra!(Sum<u16>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
impl_algebra!(Sum<u32>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
impl_algebra!(Sum<u64>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
impl_algebra!(Sum<u128>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
impl_algebra!(Sum<usize>, op: |_, a, b| a + b, id: |_| 0, commu: {}, assoc: {});
impl_algebra!(Sum<f32>, op: |_, a, b| a + b, id: |_| 0.0, inv: |_, a: f32| -a, commu: {}, assoc: {});
impl_algebra!(Sum<f64>, op: |_, a, b| a + b, id: |_| 0.0, inv: |_, a: f64| -a, commu: {}, assoc: {});
}
pub mod tuple {
pub use crate::algebra::traits::*;
#[derive(Clone, Copy, Default, Debug, PartialEq, Eq)]
pub struct Pair<A1, A2>(A1, A2);
impl<A1, A2> Pair<A1, A2> {
pub fn new(a1: A1, a2: A2) -> Self {
Self(a1, a2)
}
}
impl<A1: AlgeStruct, A2: AlgeStruct> AlgeStruct for Pair<A1, A2> {
type Output = (A1::Output, A2::Output);
}
impl<A1: BinaryOp, A2: BinaryOp> BinaryOp for Pair<A1, A2> {
fn op(&self, a: Self::Output, b: Self::Output) -> Self::Output {
(self.0.op(a.0, b.0), self.1.op(a.1, b.1))
}
}
impl<A1: Identity, A2: Identity> Identity for Pair<A1, A2> {
fn id(&self) -> Self::Output {
(self.0.id(), self.1.id())
}
}
impl<A1: Associative, A2: Associative> Associative for Pair<A1, A2> {}
}
}
pub mod algo {
pub mod bsearch {
macro_rules! bsearch_impl {
($t:tt, $a:expr, $value:expr) => {{
let n = $a.len();
let mut b = 0;
let mut len = n;
while len > 0 {
let half = len / 2;
let mid = b + half;
if &$a[mid] $t $value {
len -= half + 1;
b = mid + 1;
} else {
len = half;
}
}
b
}}
}
#[inline]
pub fn lower_bound<T: Ord>(a: &[T], value: &T) -> usize {
bsearch_impl!(<, a, value)
}
#[inline]
pub fn upper_bound<T: Ord>(a: &[T], value: &T) -> usize {
bsearch_impl!(<=, a, value)
}
#[inline]
pub fn equal_range<T: Ord>(a: &[T], value: &T) -> (usize, usize) {
(lower_bound(a, value), upper_bound(a, value))
}
}
}
pub mod ds {
pub mod persistent_segtree {
use crate::algebra::traits::Monoid;
use std::cell::RefCell;
use std::ops::Range;
use std::rc::Rc;
#[derive(Clone, Debug)]
struct Node<T> {
value: T,
left: Option<Rc<RefCell<Node<T>>>>,
right: Option<Rc<RefCell<Node<T>>>>,
}
impl<T> Node<T> {
fn new(value: T) -> Self {
Self {
value,
left: None,
right: None,
}
}
}
#[derive(Clone, Debug)]
pub struct PersistenSegtree<M: Monoid> {
root: Option<Rc<RefCell<Node<M::Output>>>>,
monoid: M,
to: usize,
}
impl<T: Clone, M: Monoid<Output = T> + Clone> PersistenSegtree<M> {
pub fn new(n: usize, monoid: M) -> Self {
let seq = vec![monoid.id(); n];
Self::from_vec(seq, monoid)
}
pub fn from_vec(a: Vec<T>, monoid: M) -> Self {
let n = a.len();
let to = if n.is_power_of_two() {
n
} else {
n.next_power_of_two()
};
let root = Some(Self::__init(0, to, &a, &monoid));
Self { root, monoid, to }
}
fn __init(from: usize, to: usize, seq: &[T], monoid: &M) -> Rc<RefCell<Node<T>>> {
if to - from == 1 {
Rc::new(RefCell::new(Node::new(seq[from].clone())))
} else {
let mid = (from + to) / 2;
let mut node = Node::new(monoid.id());
let lv = if seq.len() > from {
let left = Self::__init(from, mid, seq, monoid);
let lv = left.borrow().value.clone();
node.left = Some(left);
lv
} else {
monoid.id()
};
let rv = if seq.len() > mid {
let right = Self::__init(mid, to, seq, monoid);
let rv = right.borrow().value.clone();
node.right = Some(right);
rv
} else {
monoid.id()
};
node.value = monoid.op(lv, rv);
Rc::new(RefCell::new(node))
}
}
fn __set(
node: Rc<RefCell<Node<T>>>,
from: usize,
to: usize,
pos: usize,
value: &T,
monoid: &M,
) -> Rc<RefCell<Node<T>>> {
if to <= pos || pos + 1 <= from {
node
} else if pos <= from && to <= pos + 1 {
Rc::new(RefCell::new(Node::new(value.clone())))
} else {
let mid = (from + to) / 2;
let lp = node
.borrow()
.left
.clone()
.map(|left| Self::__set(left, from, mid, pos, value, monoid));
let rp = node
.borrow()
.right
.clone()
.map(|right| Self::__set(right, mid, to, pos, value, monoid));
let mut s = Node::new(
monoid.op(
lp.as_ref()
.map_or(monoid.id(), |l| l.borrow().value.clone()),
rp.as_ref()
.map_or(monoid.id(), |r| r.borrow().value.clone()),
),
);
s.left = lp;
s.right = rp;
Rc::new(RefCell::new(s))
}
}
pub fn assign(&self, i: usize, value: T) -> Self {
let new_root = Self::__set(
self.root.clone().unwrap(),
0,
self.to,
i,
&value,
&self.monoid,
);
Self {
root: Some(new_root),
monoid: self.monoid.clone(),
to: self.to,
}
}
fn __fold(
node: Rc<RefCell<Node<T>>>,
from: usize,
to: usize,
l: usize,
r: usize,
monoid: &M,
) -> T {
if l <= from && to <= r {
node.borrow().value.clone()
} else if to <= l || r <= from {
monoid.id()
} else {
let mid = (from + to) / 2;
let lv = node.borrow().left.clone().map_or(monoid.id(), |left| {
Self::__fold(left, from, mid, l, r, monoid)
});
let rv = node.borrow().right.clone().map_or(monoid.id(), |right| {
Self::__fold(right, mid, to, l, r, monoid)
});
monoid.op(lv, rv)
}
}
pub fn fold(&self, Range { start, end }: Range<usize>) -> T {
Self::__fold(
self.root.clone().unwrap(),
0,
self.to,
start,
end,
&self.monoid,
)
}
}
}
}
pub mod macros {
pub mod impl_algebra {
#[macro_export]
macro_rules! impl_algebra {
($t:ty, op: $f:expr) => {
impl BinaryOp for $t {
fn op(&self, a: Self::Output, b: Self::Output) -> Self::Output {
$f(&self, a, b)
}
}
};
($t:ty, id: $f:expr) => {
impl Identity for $t {
fn id(&self) -> Self::Output {
$f(&self)
}
}
};
($t:ty, inv: $f:expr) => {
impl Inverse for $t {
fn inv(&self, a: Self::Output) -> Self::Output {
$f(self, a)
}
}
};
($t:ty, commu: $f:expr) => {
impl Commutative for $t {}
};
($t:ty, assoc: $f:expr) => {
impl Associative for $t {}
};
($t:ty, idem: $f:expr) => {
impl Idempotence for $t {}
};
($t:ty, $($s:ident: $f:expr),+) => {
$(
impl_algebra!($t, $s: $f);
)+
}
}
}
pub mod io {
#[macro_export]
macro_rules! get {
( $in:ident, [$a:tt $(as $to:ty)*; $num:expr] ) => {
{
let n = $num;
(0 .. n).map(|_| get!($in, $a $(as $to)*)).collect::<Vec<_>>()
}
};
( $in:ident, ($($type:tt $(as $to:ty)*),*) ) => {
($(get!($in, $type $(as $to)*)),*)
};
( $in:ident, i8 ) => { $in.read_i64() as i8 };
( $in:ident, i16 ) => { $in.read_i64() as i16 };
( $in:ident, i32 ) => { $in.read_i64() as i32 };
( $in:ident, i64 ) => { $in.read_i64() };
( $in:ident, isize ) => { $in.read_i64() as isize };
( $in:ident, u8 ) => { $in.read_u64() as u8 };
( $in:ident, u16 ) => { $in.read_u64() as u16 };
( $in:ident, u32 ) => { $in.read_u64() as u32 };
( $in:ident, u64 ) => { $in.read_u64() };
( $in:ident, usize ) => { $in.read_u64() as usize };
( $in:ident, [char] ) => { $in.read_chars() };
( $in:ident, $from:tt as $to:ty ) => { <$to>::from(get!($in, $from)) };
}
#[macro_export]
macro_rules! input {
( @inner $in:ident, mut $name:ident : $type:tt ) => {
let mut $name = get!($in, $type);
};
( @inner $in:ident, mut $name:ident : $type:tt as $to:ty ) => {
let mut $name = get!($in, $type as $to);
};
( @inner $in:ident, $name:ident : $type:tt ) => {
let $name = get!($in, $type);
};
( @inner $in:ident, $name:ident : $type:tt as $to:ty ) => {
let $name = get!($in, $type as $to);
};
( $in:ident >> $($($names:ident)* : $type:tt $(as $to:ty)*),* ) => {
$(input!(@inner $in, $($names)* : $type $(as $to)*);)*
}
}
}
}
pub mod utils {
pub mod fastio {
use std::fmt::Display;
use std::io::{Read, Write};
pub struct FastIO {
in_bytes: Vec<u8>,
in_cur: usize,
out_buf: std::io::BufWriter<std::io::Stdout>,
}
impl FastIO {
pub fn new() -> Self {
let mut s = vec![];
std::io::stdin().read_to_end(&mut s).unwrap();
let cout = std::io::stdout();
Self {
in_bytes: s,
in_cur: 0,
out_buf: std::io::BufWriter::new(cout),
}
}
#[inline]
pub fn getc(&mut self) -> Option<u8> {
if self.in_cur < self.in_bytes.len() {
self.in_cur += 1;
Some(self.in_bytes[self.in_cur])
} else {
None
}
}
#[inline]
pub fn peek(&self) -> Option<u8> {
if self.in_cur < self.in_bytes.len() {
Some(self.in_bytes[self.in_cur])
} else {
None
}
}
#[inline]
pub fn skip(&mut self) {
while self.peek().map_or(false, |c| c.is_ascii_whitespace()) {
self.in_cur += 1;
}
}
pub fn read_u64(&mut self) -> u64 {
self.skip();
let mut ret: u64 = 0;
while self.peek().map_or(false, |c| c.is_ascii_digit()) {
ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as u64;
self.in_cur += 1;
}
ret
}
pub fn read_u32(&mut self) -> u32 {
self.read_u64() as u32
}
pub fn read_usize(&mut self) -> usize {
self.read_u64() as usize
}
pub fn read_i64(&mut self) -> i64 {
self.skip();
let mut ret: i64 = 0;
let minus = if self.peek() == Some(b'-') {
self.in_cur += 1;
true
} else {
false
};
while self.peek().map_or(false, |c| c.is_ascii_digit()) {
ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as i64;
self.in_cur += 1;
}
if minus {
ret = -ret;
}
ret
}
pub fn read_i32(&mut self) -> i32 {
self.read_i64() as i32
}
pub fn read_isize(&mut self) -> isize {
self.read_i64() as isize
}
pub fn read_f64(&mut self) -> f64 {
self.read_chars()
.into_iter()
.collect::<String>()
.parse()
.unwrap()
}
pub fn read_chars(&mut self) -> Vec<char> {
self.skip();
let mut ret = vec![];
while self.peek().map_or(false, |c| c.is_ascii_graphic()) {
ret.push(self.in_bytes[self.in_cur] as char);
self.in_cur += 1;
}
ret
}
pub fn write_rev<T: Display>(&mut self, s: T) {
let mut s = format!("{}", s);
let s = unsafe { s.as_bytes_mut() };
s.reverse();
self.out_buf.write_all(s).unwrap();
}
pub fn write<T: Display>(&mut self, s: T) {
self.out_buf.write_all(format!("{}", s).as_bytes()).unwrap();
}
pub fn writeln_rev<T: Display>(&mut self, s: T) {
self.write_rev(s);
self.out_buf.write_all(&[b'\n']).unwrap();
}
pub fn writeln<T: Display>(&mut self, s: T) {
self.write(s);
self.out_buf.write_all(&[b'\n']).unwrap();
}
}
impl Drop for FastIO {
fn drop(&mut self) {
self.out_buf.flush().unwrap();
}
}
}
pub mod join_str {
pub trait JoinStr {
fn join_str(self, _: &str) -> String;
}
impl<T, I> JoinStr for I
where
T: ToString,
I: Iterator<Item = T>,
{
fn join_str(self, s: &str) -> String {
self.map(|x| x.to_string()).collect::<Vec<_>>().join(s)
}
}
}
pub mod transpose {
pub trait Transpose {
type Output;
fn transpose(self) -> Self::Output;
}
macro_rules! impl_transpose {
($($t:tt),+; $($index:tt),+) => {
impl<$($t),+> Transpose for Vec<($($t),+)> {
type Output = ($(Vec<$t>),+);
fn transpose(self) -> Self::Output {
let mut ret = ($(Vec::<$t>::new()),+);
for x in self {
$(
ret.$index.push(x.$index);
)+
}
ret
}
}
};
}
impl_transpose!(T0, T1; 0, 1);
impl_transpose!(T0, T1, T2; 0, 1, 2);
impl_transpose!(T0, T1, T2, T3; 0, 1, 2, 3);
impl_transpose!(T0, T1, T2, T3, T4; 0, 1, 2, 3, 4);
}
}