結果
| 問題 |
No.1496 不思議な数え上げ
|
| コンテスト | |
| ユーザー |
 akakimidori
|
| 提出日時 | 2021-05-02 06:05:54 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 92 ms / 3,000 ms |
| コード長 | 7,100 bytes |
| コンパイル時間 | 12,159 ms |
| コンパイル使用メモリ | 379,756 KB |
| 実行使用メモリ | 23,168 KB |
| 最終ジャッジ日時 | 2024-07-20 14:39:12 |
| 合計ジャッジ時間 | 19,932 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 39 |
ソースコード
// ---------- begin SegmentTree Point update Range query ----------
mod segment_tree {
pub struct PURQ<T, F> {
size: usize,
data: Vec<T>,
e: T,
op: F,
}
#[allow(dead_code)]
impl<T, F> PURQ<T, F>
where
T: Clone,
F: Fn(&T, &T) -> T,
{
pub fn new(size: usize, e: T, op: F) -> PURQ<T, F> {
let size = size.next_power_of_two();
PURQ {
size,
data: vec![e.clone(); 2 * size],
e: e,
op: op,
}
}
pub fn update(&mut self, x: usize, v: T) {
assert!(x < self.size);
let mut x = x + self.size;
let data = &mut self.data;
data[x] = v;
x >>= 1;
while x > 0 {
data[x] = (self.op)(&data[2 * x], &data[2 * x + 1]);
x >>= 1;
}
}
pub fn update_tmp(&mut self, x: usize, v: T) {
assert!(x < self.size);
self.data[x + self.size] = v;
}
pub fn update_all(&mut self) {
let data = &mut self.data;
for k in (1..self.size).rev() {
data[k] = (self.op)(&data[2 * k], &data[2 * k + 1]);
}
}
pub fn find(&self, l: usize, r: usize) -> T {
assert!(l <= r && r <= self.size);
if l == r {
return self.e.clone();
}
let mut p = self.e.clone();
let mut q = self.e.clone();
let mut l = l + self.size;
let mut r = r + self.size;
let data = &self.data;
while l < r {
if l & 1 == 1 {
p = (self.op)(&p, &data[l]);
l += 1;
}
if r & 1 == 1 {
r -= 1;
q = (self.op)(&data[r], &q);
}
l >>= 1;
r >>= 1;
}
(self.op)(&p, &q)
}
}
}
// ---------- end SegmentTree Point update Range query ----------
// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let s = {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}
macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}
macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, bytes) => {
read_value!($iter, String).bytes().collect::<Vec<u8>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
// ---------- end input macro ----------
// ---------- begin super slice ----------
pub trait SuperSlice {
type Item;
fn lower_bound(&self, key: &Self::Item) -> usize
where
Self::Item: Ord;
fn lower_bound_by<F>(&self, f: F) -> usize
where
F: FnMut(&Self::Item) -> std::cmp::Ordering;
fn lower_bound_by_key<K, F>(&self, key: &K, f: F) -> usize
where
K: Ord,
F: FnMut(&Self::Item) -> K;
fn upper_bound(&self, key: &Self::Item) -> usize
where
Self::Item: Ord;
fn upper_bound_by<F>(&self, f: F) -> usize
where
F: FnMut(&Self::Item) -> std::cmp::Ordering;
fn upper_bound_by_key<K, F>(&self, key: &K, f: F) -> usize
where
K: Ord,
F: FnMut(&Self::Item) -> K;
fn reverse_lower_bound(&self, key: &Self::Item) -> usize
where
Self::Item: Ord,
{
self.lower_bound_by(|p| p.cmp(key).reverse())
}
fn reverse_upper_bound(&self, key: &Self::Item) -> usize
where
Self::Item: Ord,
{
self.upper_bound_by(|p| p.cmp(key).reverse())
}
}
impl<T> SuperSlice for [T] {
type Item = T;
fn lower_bound(&self, key: &Self::Item) -> usize
where
T: Ord,
{
self.lower_bound_by(|p| p.cmp(key))
}
fn lower_bound_by<F>(&self, mut f: F) -> usize
where
F: FnMut(&Self::Item) -> std::cmp::Ordering,
{
self.binary_search_by(|p| f(p).then(std::cmp::Ordering::Greater))
.unwrap_err()
}
fn lower_bound_by_key<K, F>(&self, key: &K, mut f: F) -> usize
where
K: Ord,
F: FnMut(&Self::Item) -> K,
{
self.lower_bound_by(|p| f(p).cmp(key))
}
fn upper_bound(&self, key: &Self::Item) -> usize
where
T: Ord,
{
self.upper_bound_by(|p| p.cmp(key))
}
fn upper_bound_by<F>(&self, mut f: F) -> usize
where
F: FnMut(&Self::Item) -> std::cmp::Ordering,
{
self.binary_search_by(|p| f(p).then(std::cmp::Ordering::Less))
.unwrap_err()
}
fn upper_bound_by_key<K, F>(&self, key: &K, mut f: F) -> usize
where
K: Ord,
F: FnMut(&Self::Item) -> K,
{
self.upper_bound_by(|p| f(p).cmp(key))
}
}
// ---------- end super slice ----------
fn run() {
input! {
n: usize,
p: [i64; n],
a: [i64; n],
}
let mut seg = segment_tree::PURQ::new(n, (n as i64, n), |a, b| std::cmp::min(*a, *b));
for (i, p) in p.iter().enumerate() {
seg.update_tmp(i, (*p, i));
}
seg.update_all();
let mut sum = p.clone();
sum.push(0);
for i in (0..n).rev() {
sum[i] += sum[i + 1];
}
let mut ans = vec![0; n];
let mut dfs = vec![(0, n)];
while let Some((l, r)) = dfs.pop() {
if l >= r {
continue;
}
let (v, x) = seg.find(l, r);
dfs.push((l, x));
dfs.push((x + 1, r));
let po = &mut ans[(v - 1) as usize];
let a = a[(v - 1) as usize];
if x - l <= r - x {
let right = &sum[(x + 1)..=r];
for &s in sum[l..=x].iter() {
*po += right.reverse_upper_bound(&(s - a));
}
} else {
let left = &sum[l..=x];
for &s in sum[(x + 1)..=r].iter() {
*po += left.len() - left.reverse_lower_bound(&(s + a));
}
}
}
use std::io::Write;
let out = std::io::stdout();
let mut out = std::io::BufWriter::new(out.lock());
for a in ans.iter() {
writeln!(out, "{}", *a).ok();
}
}
fn main() {
run();
}