結果
| 問題 | No.1233 割り切れない気持ち |
| ユーザー |
 o2c
|
| 提出日時 | 2020-09-20 21:51:25 |
| 言語 | Rust (1.77.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,008 bytes |
| コンパイル時間 | 940 ms |
| コンパイル使用メモリ | 149,492 KB |
| 実行使用メモリ | 8,752 KB |
| 最終ジャッジ日時 | 2023-09-06 16:34:30 |
| 合計ジャッジ時間 | 7,179 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 3 ms
4,380 KB |
| testcase_01 | AC | 3 ms
4,380 KB |
| testcase_02 | AC | 8 ms
4,380 KB |
| testcase_03 | AC | 20 ms
4,376 KB |
| testcase_04 | AC | 15 ms
4,376 KB |
| testcase_05 | AC | 10 ms
4,376 KB |
| testcase_06 | AC | 11 ms
4,376 KB |
| testcase_07 | AC | 30 ms
4,380 KB |
| testcase_08 | AC | 33 ms
4,380 KB |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | AC | 28 ms
4,380 KB |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | TLE | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
コンパイルメッセージ
warning: variable does not need to be mutable
--> Main.rs:14:338
|
14 | ...es !read {($($t :tt ) ,*;$n :expr ) =>{{let stdin =::std ::io ::stdin () ;let ret =::std ::io ::BufRead ::lines (stdin .lock () ) .take ($n ) .map (|line |{let line =line .unwrap () ;let mut it =line .split_whitespace () ;_read !(it ;$($t ) ,*) } ) .collect ::<Vec <_ >>() ;ret } } ;($($t :tt ) ,*) =>{{let line =readln () ;let mut it =l...
| ----^^
| |
| help: remove this `mut`
...
24 | ... = read!([usize]);
| -------------- in this macro invocation
|
= note: `#[warn(unused_mut)]` on by default
= note: this warning originates in the macro `read` (in Nightly builds, run with -Z macro-backtrace for more info)
warning: 1 warning emitted
ソースコード
#[allow(unused_imports)]
use {std::cmp::*, std::collections::*, std::io::Write, std::ops::*};
#[allow(unused_macros)]
macro_rules! dbg { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; }
pub fn readln() -> String {
let mut line = String::new();
::std::io::stdin()
.read_line(&mut line)
.unwrap_or_else(|e| panic!("{}", e));
line
}
macro_rules !read {($($t :tt ) ,*;$n :expr ) =>{{let stdin =::std ::io ::stdin () ;let ret =::std ::io ::BufRead ::lines (stdin .lock () ) .take ($n ) .map (|line |{let line =line .unwrap () ;let mut it =line .split_whitespace () ;_read !(it ;$($t ) ,*) } ) .collect ::<Vec <_ >>() ;ret } } ;($($t :tt ) ,*) =>{{let line =readln () ;let mut it =line .split_whitespace () ;_read !(it ;$($t ) ,*) } } ;}
macro_rules !_read {($it :ident ;[char ] ) =>{_read !($it ;String ) .chars () .collect ::<Vec <_ >>() } ;($it :ident ;[u8 ] ) =>{Vec ::from (_read !($it ;String ) .into_bytes () ) } ;($it :ident ;usize1 ) =>{$it .next () .unwrap_or_else (||panic !("input mismatch" ) ) .parse ::<usize >() .unwrap_or_else (|e |panic !("{}" ,e ) ) -1 } ;($it :ident ;[usize1 ] ) =>{$it .map (|s |s .parse ::<usize >() .unwrap_or_else (|e |panic !("{}" ,e ) ) -1 ) .collect ::<Vec <_ >>() } ;($it :ident ;[$t :ty ] ) =>{$it .map (|s |s .parse ::<$t >() .unwrap_or_else (|e |panic !("{}" ,e ) ) ) .collect ::<Vec <_ >>() } ;($it :ident ;$t :ty ) =>{$it .next () .unwrap_or_else (||panic !("input mismatch" ) ) .parse ::<$t >() .unwrap_or_else (|e |panic !("{}" ,e ) ) } ;($it :ident ;$($t :tt ) ,+) =>{($(_read !($it ;$t ) ) ,*) } ;}
#[allow(unused_macros)]
macro_rules !max {($a :expr $(,) *) =>{{$a } } ;($a :expr ,$b :expr $(,) *) =>{{std ::cmp ::max ($a ,$b ) } } ;($a :expr ,$($rest :expr ) ,+$(,) *) =>{{std ::cmp ::max ($a ,max !($($rest ) ,+) ) } } ;}
#[allow(unused_macros)]
macro_rules !chmax {($base :expr ,$($cmps :expr ) ,+$(,) *) =>{{let cmp_max =max !($($cmps ) ,+) ;if $base <cmp_max {$base =cmp_max ;true } else {false } } } ;}
fn main() {
let n = read!(usize);
let a = read!([usize]);
let s: usize = a.iter().sum();
let mut ans = n * s;
let mut bit = FenwickTree::<usize>::new(100001, 0);
for i in 0..n {
bit.add(a[i], 1);
}
for i in 0..n {
let a = a[i];
for j in 0.. {
if (j + 1) * a <= 100000 {
ans -= j * a * bit.sum(j * a..(j + 1) * a);
} else if j * a <= 100000 {
ans -= j * a * bit.sum(j * a..);
} else {
break;
}
}
}
println!("{}", ans);
}
struct FenwickTree<T> {
n: usize,
tree: Vec<T>,
e: T,
}
#[allow(dead_code)]
impl<T: std::ops::AddAssign + Clone> FenwickTree<T> {
fn new(n: usize, e: T) -> Self {
FenwickTree {
n,
tree: vec![e.clone(); n],
e,
}
}
/// A[i] += w
fn add<U: Clone>(&mut self, mut idx: usize, w: U)
where
T: std::ops::AddAssign<U>,
{
idx += 1;
while idx <= self.n {
self.tree[idx - 1] += w.clone();
idx += idx & idx.wrapping_neg();
}
}
/// return A[0] + ... + A[idx-1]
fn accum(&self, mut idx: usize) -> T {
let mut sum = self.e.clone();
while idx > 0 {
sum += self.tree[idx - 1].clone();
idx &= idx - 1;
}
sum
}
/// return ∑ d[i] for i in R
fn sum<R>(&self, interval: R) -> T
where
T: std::ops::Sub<Output = T>,
R: std::ops::RangeBounds<usize>,
{
let r = match interval.end_bound() {
std::ops::Bound::Excluded(&a) => a,
std::ops::Bound::Included(&a) => a + 1,
_ => self.n,
};
match interval.start_bound() {
std::ops::Bound::Included(&l) => self.accum(r) - self.accum(l),
_ => self.accum(r),
}
}
}