結果
問題 | No.1300 Sum of Inversions |
ユーザー | fukafukatani |
提出日時 | 2020-11-27 23:42:58 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 695 ms / 2,000 ms |
コード長 | 8,757 bytes |
コンパイル時間 | 2,211 ms |
コンパイル使用メモリ | 174,464 KB |
実行使用メモリ | 30,596 KB |
最終ジャッジ日時 | 2023-10-09 21:20:39 |
合計ジャッジ時間 | 20,567 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 1 ms
4,352 KB |
testcase_02 | AC | 1 ms
4,352 KB |
testcase_03 | AC | 543 ms
27,000 KB |
testcase_04 | AC | 539 ms
26,684 KB |
testcase_05 | AC | 422 ms
20,056 KB |
testcase_06 | AC | 624 ms
28,584 KB |
testcase_07 | AC | 594 ms
27,984 KB |
testcase_08 | AC | 645 ms
29,256 KB |
testcase_09 | AC | 658 ms
29,360 KB |
testcase_10 | AC | 312 ms
16,564 KB |
testcase_11 | AC | 307 ms
16,664 KB |
testcase_12 | AC | 516 ms
26,816 KB |
testcase_13 | AC | 500 ms
26,400 KB |
testcase_14 | AC | 695 ms
30,508 KB |
testcase_15 | AC | 621 ms
29,112 KB |
testcase_16 | AC | 529 ms
27,956 KB |
testcase_17 | AC | 300 ms
16,304 KB |
testcase_18 | AC | 340 ms
17,152 KB |
testcase_19 | AC | 444 ms
25,332 KB |
testcase_20 | AC | 459 ms
25,604 KB |
testcase_21 | AC | 450 ms
25,476 KB |
testcase_22 | AC | 395 ms
20,080 KB |
testcase_23 | AC | 587 ms
28,480 KB |
testcase_24 | AC | 409 ms
20,380 KB |
testcase_25 | AC | 337 ms
16,908 KB |
testcase_26 | AC | 331 ms
16,868 KB |
testcase_27 | AC | 377 ms
19,804 KB |
testcase_28 | AC | 634 ms
29,704 KB |
testcase_29 | AC | 437 ms
25,484 KB |
testcase_30 | AC | 624 ms
29,172 KB |
testcase_31 | AC | 379 ms
20,276 KB |
testcase_32 | AC | 418 ms
20,596 KB |
testcase_33 | AC | 32 ms
11,180 KB |
testcase_34 | AC | 39 ms
11,260 KB |
testcase_35 | AC | 435 ms
30,596 KB |
testcase_36 | AC | 438 ms
30,596 KB |
コンパイルメッセージ
warning: associated function `set_modulus` is never used --> Main.rs:91:8 | 91 | fn set_modulus(m: i64) { | ^^^^^^^^^^^ | = note: `#[warn(dead_code)]` on by default warning: associated function `pow` is never used --> Main.rs:109:8 | 109 | fn pow(self, p: i64) -> Modulo { | ^^^ warning: associated function `inv` is never used --> Main.rs:121:8 | 121 | fn inv(self) -> Modulo { | ^^^ warning: 3 warnings emitted
ソースコード
#![allow(unused_imports)] use std::cmp::*; use std::collections::*; use std::io::Write; use std::ops::Bound::*; #[allow(unused_macros)] macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; } fn main() { let n = read::<usize>(); let a = read_vec::<i64>() .iter() .map(|&x| Modulo(x)) .collect::<Vec<_>>(); let mut a_clone = a.clone(); a_clone.sort(); a_clone.dedup(); let mut compress_dict = HashMap::new(); for i in 0..a_clone.len() { compress_dict.insert(a_clone[i], i); } let mut from_left = vec![Modulo(0); n]; let mut from_left_count = vec![0i64; n]; let mut seg = SegTree::new(compress_dict.len(), Modulo(0), |a, b| a + b); let mut seg_count = SegTree::new(compress_dict.len(), 0, |a, b| a + b); for i in 0..n { let cur = compress_dict[&a[i]]; from_left[i] = seg.query(cur + 1, compress_dict.len()); let val = seg.query(cur, cur + 1); seg.update(cur, val + a[i]); from_left_count[i] = seg_count.query(cur + 1, compress_dict.len()); let val = seg_count.query(cur, cur + 1); seg_count.update(cur, val + 1); } let mut from_right = vec![Modulo(0); n]; let mut from_right_count = vec![0i64; n]; let mut seg = SegTree::new(compress_dict.len(), Modulo(0), |a, b| a + b); let mut seg_count = SegTree::new(compress_dict.len(), 0, |a, b| a + b); for i in (0..n).rev() { let cur = compress_dict[&a[i]]; from_right[i] = seg.query(0, cur); let val = seg.query(cur, cur + 1); seg.update(cur, val + a[i]); from_right_count[i] = seg_count.query(0, cur); let val = seg_count.query(cur, cur + 1); seg_count.update(cur, val + 1); } // debug!(from_left); // debug!(from_right); let mut ans = Modulo(0); for i in 0..n { ans += from_left[i] * from_right_count[i]; ans += from_right[i] * from_left_count[i]; ans += a[i] * from_right_count[i] * from_left_count[i]; } println!("{}", ans); } fn read<T: std::str::FromStr>() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)] struct Modulo(i64); static mut MODULUS: i64 = 998244353; impl Modulo { fn set_modulus(m: i64) { unsafe { MODULUS = m; } } fn get_modulus() -> i64 { unsafe { MODULUS } } fn new(x: i64) -> Modulo { let m = Modulo::get_modulus(); if x < 0 { Modulo(x % m + m) } else if x < m { Modulo(x) } else { Modulo(x % m) } } fn pow(self, p: i64) -> Modulo { if p == 0 { Modulo(1) } else { let mut t = self.pow(p / 2); t *= t; if p & 1 == 1 { t *= self; } t } } fn inv(self) -> Modulo { self.pow(Modulo::get_modulus() - 2) } } impl std::fmt::Display for Modulo { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { self.0.fmt(f) } } impl std::ops::AddAssign for Modulo { fn add_assign(&mut self, other: Modulo) { let m = Modulo::get_modulus(); self.0 += other.0; if self.0 >= m { self.0 -= m; } } } impl std::ops::MulAssign for Modulo { fn mul_assign(&mut self, other: Modulo) { let m = Modulo::get_modulus(); self.0 *= other.0; self.0 %= m; } } impl std::ops::SubAssign for Modulo { fn sub_assign(&mut self, other: Modulo) { let m = Modulo::get_modulus(); self.0 += m - other.0; if self.0 >= m { self.0 -= m; } } } macro_rules! impl_modulo_ops { ($imp:ident, $method:ident, $assign_imp:ident, $assign_method:ident) => { impl<'a> std::ops::$assign_imp<&'a Modulo> for Modulo { fn $assign_method(&mut self, other: &'a Modulo) { std::ops::$assign_imp::$assign_method(self, *other); } } impl std::ops::$imp for Modulo { type Output = Modulo; fn $method(self, other: Modulo) -> Modulo { let mut x = self; std::ops::$assign_imp::$assign_method(&mut x, other); x } } impl<'a> std::ops::$imp<Modulo> for &'a Modulo { type Output = Modulo; fn $method(self, other: Modulo) -> Modulo { std::ops::$imp::$method(*self, other) } } impl<'a> std::ops::$imp<&'a Modulo> for Modulo { type Output = Modulo; fn $method(self, other: &'a Modulo) -> Modulo { std::ops::$imp::$method(self, *other) } } impl<'a, 'b> std::ops::$imp<&'b Modulo> for &'a Modulo { type Output = Modulo; fn $method(self, other: &'b Modulo) -> Modulo { std::ops::$imp::$method(*self, *other) } } impl std::ops::$assign_imp<i64> for Modulo { fn $assign_method(&mut self, other: i64) { std::ops::$assign_imp::$assign_method(self, Modulo::new(other)); } } impl<'a> std::ops::$assign_imp<&'a i64> for Modulo { fn $assign_method(&mut self, other: &'a i64) { std::ops::$assign_imp::$assign_method(self, *other); } } impl std::ops::$imp<i64> for Modulo { type Output = Modulo; fn $method(self, other: i64) -> Modulo { let mut x = self; std::ops::$assign_imp::$assign_method(&mut x, other); x } } impl<'a> std::ops::$imp<&'a i64> for Modulo { type Output = Modulo; fn $method(self, other: &'a i64) -> Modulo { std::ops::$imp::$method(self, *other) } } impl<'a> std::ops::$imp<i64> for &'a Modulo { type Output = Modulo; fn $method(self, other: i64) -> Modulo { std::ops::$imp::$method(*self, other) } } impl<'a, 'b> std::ops::$imp<&'b i64> for &'a Modulo { type Output = Modulo; fn $method(self, other: &'b i64) -> Modulo { std::ops::$imp::$method(*self, *other) } } }; } impl_modulo_ops!(Add, add, AddAssign, add_assign); impl_modulo_ops!(Mul, mul, MulAssign, mul_assign); impl_modulo_ops!(Sub, sub, SubAssign, sub_assign); use std::iter::Sum; impl Sum for Modulo { fn sum<I>(iter: I) -> Self where I: Iterator<Item = Modulo>, { iter.fold(Modulo(0), |a, b| a + b) } } impl<'a> Sum<&'a Modulo> for Modulo { fn sum<I>(iter: I) -> Self where I: Iterator<Item = &'a Self>, { iter.fold(Modulo(0), |a, b| a + b) } } #[derive(Clone)] struct SegTree<T, F> where F: Fn(T, T) -> T, T: std::clone::Clone + std::marker::Copy, { n: usize, dat: Vec<T>, init: T, functor: F, } impl<T, F> SegTree<T, F> where F: Fn(T, T) -> T, T: std::clone::Clone + std::marker::Copy, { fn new(n: usize, init: T, f: F) -> SegTree<T, F> { let mut m = 1; // For simplicity, we use 2 ** n sized SegTree. while m < n { m *= 2; } SegTree { n: m, dat: vec![init; 2 * m - 1], init: init, functor: f, } } // dat[k] = a; fn update(&mut self, k: usize, a: T) { let mut k = k; k += self.n - 1; self.dat[k] = a; while k > 0 { k = (k - 1) / 2; self.dat[k] = (self.functor)(self.dat[k * 2 + 1], self.dat[k * 2 + 2]); } } // [a, b) fn query(&self, a: usize, b: usize) -> T { self.query_inner(a, b, 0, 0, self.n) } fn query_inner(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> T { if r <= a || b <= l { return self.init; } if a <= l && r <= b { return self.dat[k]; } let vl = self.query_inner(a, b, k * 2 + 1, l, (l + r) / 2); let vr = self.query_inner(a, b, k * 2 + 2, (l + r) / 2, r); (self.functor)(vl, vr) } }