結果
問題 | No.1558 Derby Live |
ユーザー | phspls |
提出日時 | 2022-11-12 12:24:56 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 245 ms / 2,000 ms |
コード長 | 3,338 bytes |
コンパイル時間 | 2,077 ms |
コンパイル使用メモリ | 156,208 KB |
実行使用メモリ | 17,780 KB |
最終ジャッジ日時 | 2023-10-12 04:27:06 |
合計ジャッジ時間 | 13,962 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 245 ms
13,508 KB |
testcase_01 | AC | 212 ms
17,780 KB |
testcase_02 | AC | 1 ms
4,352 KB |
testcase_03 | AC | 152 ms
8,504 KB |
testcase_04 | AC | 74 ms
5,352 KB |
testcase_05 | AC | 93 ms
5,592 KB |
testcase_06 | AC | 148 ms
9,032 KB |
testcase_07 | AC | 5 ms
4,348 KB |
testcase_08 | AC | 148 ms
9,072 KB |
testcase_09 | AC | 155 ms
10,396 KB |
testcase_10 | AC | 156 ms
10,916 KB |
testcase_11 | AC | 162 ms
10,892 KB |
testcase_12 | AC | 170 ms
11,456 KB |
testcase_13 | AC | 174 ms
11,392 KB |
testcase_14 | AC | 177 ms
11,984 KB |
testcase_15 | AC | 180 ms
11,980 KB |
testcase_16 | AC | 184 ms
12,528 KB |
testcase_17 | AC | 194 ms
15,348 KB |
testcase_18 | AC | 216 ms
15,924 KB |
testcase_19 | AC | 219 ms
15,912 KB |
testcase_20 | AC | 228 ms
16,408 KB |
testcase_21 | AC | 219 ms
15,880 KB |
testcase_22 | AC | 221 ms
15,912 KB |
testcase_23 | AC | 229 ms
16,476 KB |
testcase_24 | AC | 219 ms
15,912 KB |
testcase_25 | AC | 218 ms
15,904 KB |
testcase_26 | AC | 226 ms
16,468 KB |
testcase_27 | AC | 217 ms
15,944 KB |
testcase_28 | AC | 221 ms
15,884 KB |
testcase_29 | AC | 224 ms
16,468 KB |
testcase_30 | AC | 218 ms
15,940 KB |
testcase_31 | AC | 221 ms
15,940 KB |
testcase_32 | AC | 222 ms
16,396 KB |
testcase_33 | AC | 1 ms
4,372 KB |
testcase_34 | AC | 1 ms
4,376 KB |
コンパイルメッセージ
warning: field `orgn` is never read --> Main.rs:5:5 | 3 | struct SegmentTree<F, T> { | ----------- field in this struct 4 | n: usize, 5 | orgn: usize, | ^^^^ | = note: `SegmentTree` has derived impls for the traits `Clone` and `Debug`, but these are intentionally ignored during dead code analysis = note: `#[warn(dead_code)]` on by default warning: associated function `get` is never used --> Main.rs:44:8 | 44 | fn get(&mut self, pos: usize) -> &T { | ^^^ warning: variable `UNIT` should have a snake case name --> Main.rs:84:9 | 84 | let UNIT = (0..n).collect::<Vec<_>>(); | ^^^^ help: convert the identifier to snake case: `unit` | = note: `#[warn(non_snake_case)]` on by default warning: 3 warnings emitted
ソースコード
#[derive(Debug, Clone)] struct SegmentTree<F, T> { n: usize, orgn: usize, unit: T, mem: Vec<T>, operator: F } impl<F, T> SegmentTree<F, T> where T: std::fmt::Debug + Clone, F: Fn(&T, &T) -> T { fn new(n: usize, unit: T, operator: F) -> Self { let mut size = 1usize; while size < n { size *= 2; } Self { n: size, orgn: n, unit: unit.clone(), mem: vec![unit.clone().to_owned(); size*2-1], operator: operator, } } fn find_closed(&self, l: usize, r: usize) -> T { self.find(l, r+1) } fn find(&self, l: usize, r: usize) -> T { self._find(l, r, 0, 0, self.n) } fn set(&mut self, pos: usize, val: T) { let mut pos = pos + self.n - 1; self.mem[pos] = val; while pos > 0 { pos = self._parent(pos); self.mem[pos] = (self.operator)(&self.mem[self._left(pos)], &self.mem[self._right(pos)]).clone().to_owned(); } } fn get(&mut self, pos: usize) -> &T { &self.mem[pos + self.n - 1] } fn _find(&self, a: usize, b: usize, nodenum: usize, l: usize, r: usize) -> T { if r <= a || b <= l { return self.unit.clone(); } else if a <= l && r <= b { return self.mem[nodenum].clone(); } let left = self._find(a, b, self._left(nodenum), l, (l+r)/2); let right = self._find(a, b, self._right(nodenum), (l+r)/2, r); (self.operator)(&left, &right) } fn _left(&self, k: usize) -> usize { 2*k+1 } fn _right(&self, k: usize) -> usize { 2*k+2 } fn _parent(&self, k: usize) -> usize { (k-1)/2 } } fn main() { let mut nmq = String::new(); std::io::stdin().read_line(&mut nmq).ok(); let nmq: Vec<usize> = nmq.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let n = nmq[0]; let m = nmq[1]; let q = nmq[2]; let queries = (0..q).map(|_| { let mut temp = String::new(); std::io::stdin().read_line(&mut temp).ok(); let temp: Vec<usize> = temp.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); temp }) .collect::<Vec<_>>(); let UNIT = (0..n).collect::<Vec<_>>(); let operator = |l: &Vec<usize>, r: &Vec<usize>| { let n = l.len(); let mut ret = vec![0usize; n]; for i in 0..n { ret[i] = r[l[i]]; } ret }; let mut segtree = SegmentTree::new(m, UNIT, operator); for v in queries.iter() { let t = v[0]; if t == 1 { let idx = v[1]-1; let order = v.iter().skip(2).map(|&v| v-1).collect::<Vec<_>>(); segtree.set(idx, order); } else if t == 2 { let r = v[1]; let val = segtree.find(0, r); let mut res = vec![0usize; n]; for i in 0..n { res[val[i]] = i+1; } println!("{}", res.iter().map(|&v| v.to_string()).collect::<Vec<_>>().join(" ")); } else { let l = v[1]-1; let r = v[2]-1; let val = segtree.find_closed(l, r); println!("{}", (0..n).map(|i| (i as isize - val[i] as isize).abs()).sum::<isize>()); } } }