結果
| 問題 |
No.2938 Sigma Sigma Distance Distance Problem
|
| コンテスト | |
| ユーザー |
 magurofly
|
| 提出日時 | 2024-10-19 17:18:26 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,885 bytes |
| コンパイル時間 | 13,700 ms |
| コンパイル使用メモリ | 402,148 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-10-19 17:18:41 |
| 合計ジャッジ時間 | 13,845 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 3 |
| other | AC * 2 WA * 18 |
コンパイルメッセージ
warning: variable `N` should have a snake case name --> src/main.rs:3:3 | 3 | N: usize, | ^ help: convert the identifier to snake case: `n` | = note: `#[warn(non_snake_case)]` on by default warning: variable `A` should have a snake case name --> src/main.rs:4:3 | 4 | A: [usize; N], | ^ help: convert the identifier to snake case: `a`
ソースコード
fn main() {
proconio::input! {
N: usize,
A: [usize; N],
}
struct Sum;
impl SegTreeHelper for Sum {
type S = (usize, usize, usize);
fn op(x: &Self::S, y: &Self::S) -> Self::S { (x.0 + y.0, x.1 + y.1, x.2 + y.2) }
fn e() -> Self::S { (0, 0, 0) }
type F = ();
}
let mut seg = SegTree::<Sum>::new(501);
let mut ans = 0usize;
for j in 1 .. N {
let (s, c, i) = seg.get(A[j - 1]);
seg.set(A[j - 1], (s + A[j - 1], c + 1, i + (j - 1)));
let (s1, c1, i1) = seg.prod(.. A[j]);
let (s2, c2, i2) = seg.prod(A[j] + 1 ..);
ans += (A[j] * c1 - s1) * (j * c1 - i1);
ans += (s2 - A[j] * c2) * (j * c2 - i2);
}
println!("{ans}");
}
use segtree::*;
pub mod segtree {
// Update: 2022-10-29 12:45
#[allow(unused_variables)]
pub trait SegTreeHelper {
/// 要素の型
type S: Clone;
/// 要素の二項演算
fn op(x: &Self::S, y: &Self::S) -> Self::S;
/// 要素の単位元
fn e() -> Self::S;
/// 作用の型（使わない場合は `()` とする）
type F: Clone + Default;
/// 要素に作用させる
fn map(f: &Self::F, x: &Self::S) -> Self::S { x.clone() }
/// 作用の単位元
fn id() -> Self::F { Self::F::default() }
/// 作用の合成
fn compose(f: &Self::F, g: &Self::F) -> Self::F { g.clone() }
/// 再計算が必要か
fn is_failed(x: &Self::S) -> bool { false }
}
pub struct SegTree<H: SegTreeHelper> {
len: usize,
size: usize,
log: u32,
data: UnsafeCell<Vec<H::S>>,
lazy: UnsafeCell<Vec<H::F>>,
}
impl<H: SegTreeHelper> SegTree<H> {
/// 長さが `len` 、要素が全て `H::e()` となるセグメント木を作成する。
pub fn new(len: usize) -> Self {
assert!(len > 0);
let size = len.next_power_of_two();
let log = size.trailing_zeros();
Self {
len, size, log,
data: UnsafeCell::new(vec![H::e(); size * 2]),
lazy: UnsafeCell::new(vec![H::id(); size]),
}
}
/// `p` 番目の要素を取得する。
pub fn get(&self, p: usize) -> H::S { self[p].clone() }
/// `p` 番目の要素に `x` を代入する。
pub fn set(&mut self, mut p: usize, x: H::S) {
assert!(p < self.len);
p += self.size;
for i in (1 ..= self.log).rev() { self.push(p >> i); }
self.data_mut()[p] = x;
for i in 1 ..= self.log { self.update(p >> i); }
}
/// `range` に含まれる要素の積を取得する。
pub fn prod(&self, range: impl RangeBounds<usize>) -> H::S {
let (mut l, mut r) = self.range(range);
assert!(l <= r);
assert!(r <= self.len);
l += self.size;
r += self.size;
if l == r { return H::e(); }
for i in (1 ..= self.log).rev() {
if (l >> i) << i != l { self.push(l >> i); }
if (r >> i) << i != r { self.push(r - 1 >> i); }
}
let mut x = H::e();
let mut y = H::e();
while l < r {
if l & 1 != 0 {
x = H::op(&x, &self.data()[l]);
l += 1;
}
l >>= 1;
if r & 1 != 0 {
y = H::op(&self.data()[r - 1], &y);
}
r >>= 1;
}
H::op(&x, &y)
}
/// 全体の積を取得する。
pub fn all_prod(&self) -> H::S { self.data()[1].clone() }
/// `p` 番目の要素に `f` を適用する。
pub fn apply(&mut self, p: usize, f: &H::F) {
assert!(p < self.len);
let x = H::map(f, &self[p]);
self.set(p, x);
}
/// `range` に含まれる要素に `f` を適用する。
pub fn apply_range(&mut self, range: impl RangeBounds<usize>, f: &H::F) {
let (mut l, mut r) = self.range(range);
assert!(l <= r);
assert!(r <= self.len);
l += self.size;
r += self.size;
for i in (1 ..= self.log).rev() {
if (l >> i) << i != l { self.push(l >> i); }
if (r >> i) << i != r { self.push(r - 1 >> i); }
}
let (l, r) = {
let (l2, r2) = (l, r);
while l < r {
if l & 1 != 0 {
self.all_apply(l, f);
l += 1;
}
l >>= 1;
if r & 1 != 0 {
self.all_apply(r - 1, f);
}
r >>= 1;
}
(l2, r2)
};
for i in 1 ..= self.log {
if (l >> i) << i != l { self.update(l >> i); }
if (r >> i) << i != r { self.update(r - 1 >> i); }
}
}
pub fn max_right(&self, mut l: usize, mut predicate: impl FnMut(&H::S) -> bool) -> usize {
assert!(l <= self.len);
assert!(predicate(&H::e()));
if l == self.len { return self.len; }
l += self.size;
for i in (1 ..= self.log).rev() { self.push(l >> i); }
let mut x = H::e();
loop {
l >>= l.trailing_zeros();
if !predicate(&H::op(&x, &self.data()[l])) {
while l < self.size {
self.push(l);
l *= 2;
let y = H::op(&x, &self.data()[l]);
if predicate(&y) {
x = y;
l += 1;
}
}
return l - self.size;
}
x = H::op(&x, &self.data()[l]);
l += 1;
if l.is_power_of_two() {
break;
}
}
self.len
}
pub fn min_left(&self, mut r: usize, mut predicate: impl FnMut(&H::S) -> bool) -> usize {
assert!(r <= self.len);
assert!(predicate(&H::e()));
if r == 0 { return 0; }
r += self.size;
for i in (1 ..= self.log).rev() { self.push(r - 1 >> i); }
let mut x = H::e();
loop {
r -= 1;
r >>= r.trailing_zeros();
if !predicate(&H::op(&self.data()[r], &x)) {
while r < self.size {
self.push(r);
r = 2 * r + 1;
let y = H::op(&self.data()[r], &x);
if predicate(&y) {
x = y;
r -= 1;
}
}
return r + 1 - self.size;
}
x = H::op(&self.data()[r], &x);
if r.is_power_of_two() {
break;
}
}
0
}
fn update(&self, k: usize) {
let z = H::op(&self.data()[k * 2], &self.data()[k * 2 + 1]);
self.data_mut()[k] = z;
}
fn all_apply(&self, k: usize, f: &H::F) {
let y = H::map(f, &self.data()[k]);
self.data_mut()[k] = y;
if k < self.size {
let h = H::compose(&self.lazy()[k], f);
self.lazy_mut()[k] = h;
if H::is_failed(&self.data()[k]) {
self.push(k);
self.update(k);
}
}
}
fn push(&self, k: usize) {
self.all_apply(2 * k, &self.lazy()[k]);
self.all_apply(2 * k + 1, &self.lazy()[k]);
self.lazy_mut()[k] = H::id();
}
fn range(&self, range: impl RangeBounds<usize>) -> (usize, usize) {
use Bound::*;
(match range.start_bound() { Included(&p) => p, Excluded(&p) => p + 1, Unbounded => 0 },
match range.end_bound() { Included(&p) => p + 1, Excluded(&p) => p, Unbounded => self.len })
}
fn data(&self) -> &Vec<H::S> { unsafe { &*self.data.get() } }
fn lazy(&self) -> &Vec<H::F> { unsafe { &*self.lazy.get() } }
fn data_mut(&self) -> &mut Vec<H::S> { unsafe { &mut *self.data.get() } }
fn lazy_mut(&self) -> &mut Vec<H::F> { unsafe { &mut *self.lazy.get() } }
}
impl<H: SegTreeHelper> From<Vec<H::S>> for SegTree<H> {
fn from(xs: Vec<H::S>) -> Self {
let this = Self::new(xs.len());
for (p, x) in xs.into_iter().enumerate() {
this.data_mut()[this.size + p] = x;
}
for k in (1 .. this.size).rev() { this.update(k); }
this
}
}
impl<H: SegTreeHelper> FromIterator<H::S> for SegTree<H> {
fn from_iter<T: IntoIterator<Item = H::S>>(iter: T) -> Self {
Self::from(iter.into_iter().collect::<Vec<_>>())
}
}
impl<H: SegTreeHelper> Index<usize> for SegTree<H> {
type Output = H::S;
fn index(&self, mut p: usize) -> &H::S {
assert!(p < self.len);
p += self.size;
for i in (1 ..= self.log).rev() { self.push(p >> i); }
&self.data()[p]
}
}
impl<H: SegTreeHelper> Debug for SegTree<H> where H::S: Debug, H::F: Debug {
fn fmt(&self, f: &mut Formatter<'_>) -> Result {
f.write_fmt(format_args!("len={}, size={}, log={}, e={:?}, id={:?}\n", self.len, self.size, self.log, H::e(), H::id()))?;
let data_str = self.data().iter().map(|x| format!("{:?}", x)).collect::<Vec<_>>();
let lazy_str = self.lazy().iter().map(|x| format!("({:?})", x)).collect::<Vec<_>>();
let unit_width = lazy_str.iter().chain(data_str.iter()).map(String::len).max().unwrap();
fn print_row(f: &mut Formatter<'_>, raw_row: &[String], pad: usize) -> Result {
let mut row = vec![];
for raw in raw_row { row.push(format!("{:^width$}", raw, width=pad)); }
f.write_str("|")?;
f.write_str(&row.join("|"))?;
f.write_str("|\n")
}
for i in 0 .. self.log {
print_row(f, &data_str[1 << i .. 2 << i], (unit_width + 1) * (1 << self.log - i) - 1)?;
print_row(f, &lazy_str[1 << i .. 2 << i], (unit_width + 1) * (1 << self.log - i) - 1)?;
}
print_row(f, &data_str[self.size ..], unit_width)?;
Ok(())
}
}
use std::{cell::*, fmt::*, iter::*, ops::*};
}