結果
問題 | No.2462 七人カノン |
ユーザー | naut3 |
提出日時 | 2023-09-09 20:40:36 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 80 ms / 2,000 ms |
コード長 | 5,400 bytes |
コンパイル時間 | 18,738 ms |
コンパイル使用メモリ | 405,848 KB |
実行使用メモリ | 12,476 KB |
最終ジャッジ日時 | 2024-06-27 13:12:51 |
合計ジャッジ時間 | 25,934 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 7 ms
5,248 KB |
testcase_01 | AC | 8 ms
5,376 KB |
testcase_02 | AC | 8 ms
5,376 KB |
testcase_03 | AC | 8 ms
5,376 KB |
testcase_04 | AC | 9 ms
5,376 KB |
testcase_05 | AC | 8 ms
5,376 KB |
testcase_06 | AC | 9 ms
5,376 KB |
testcase_07 | AC | 9 ms
5,376 KB |
testcase_08 | AC | 9 ms
5,376 KB |
testcase_09 | AC | 8 ms
5,376 KB |
testcase_10 | AC | 8 ms
5,376 KB |
testcase_11 | AC | 8 ms
5,376 KB |
testcase_12 | AC | 9 ms
5,376 KB |
testcase_13 | AC | 70 ms
10,420 KB |
testcase_14 | AC | 73 ms
11,628 KB |
testcase_15 | AC | 70 ms
10,704 KB |
testcase_16 | AC | 80 ms
11,716 KB |
testcase_17 | AC | 79 ms
11,712 KB |
testcase_18 | AC | 19 ms
9,856 KB |
testcase_19 | AC | 20 ms
9,984 KB |
testcase_20 | AC | 68 ms
12,224 KB |
testcase_21 | AC | 68 ms
12,228 KB |
testcase_22 | AC | 69 ms
12,348 KB |
testcase_23 | AC | 70 ms
12,224 KB |
testcase_24 | AC | 51 ms
11,452 KB |
testcase_25 | AC | 78 ms
12,476 KB |
コンパイルメッセージ
warning: method `get_point` is never used --> src/main.rs:141:16 | 117 | impl<T: Clone + Copy> Segmenttree<T> { | ------------------------------------ method in this implementation ... 141 | fn get_point(&self, p: usize) -> T { | ^^^^^^^^^ | = note: `#[warn(dead_code)]` on by default
ソースコード
#![allow(non_snake_case, unused_imports, unused_must_use)] use std::io::{self, prelude::*}; use std::str; fn main() { let (stdin, stdout) = (io::stdin(), io::stdout()); let mut scan = Scanner::new(stdin.lock()); let mut out = io::BufWriter::new(stdout.lock()); macro_rules! input { ($T: ty) => { scan.token::<$T>() }; ($T: ty, $N: expr) => { (0..$N).map(|_| scan.token::<$T>()).collect::<Vec<_>>() }; } let N = input!(usize); let Q = input!(usize); let IST = (0..Q) .map(|_| (input!(usize) - 1, input!(usize), input!(usize))) .collect::<Vec<_>>(); let mut point = vec![0.0; 100_010]; { let mut stree = SegmentTree::new(100_010, |x, y| x + y, 0); for &(_, s, t) in IST.iter() { stree.apply(s, t, 1); } for i in 0..100_010 { let c = stree.get(i); point[i] = 1.0 / c as f64; } struct SegmentTree<T> { size: usize, tree: Vec<T>, op: fn(T, T) -> T, } impl<T: Clone + Copy> SegmentTree<T> { fn new(n: usize, op: fn(T, T) -> T, id: T) -> Self { Self { size: n, tree: vec![id; n + n], op: op, } } fn get(&self, mut p: usize) -> T { p += self.size; let mut ret = self.tree[p]; while p > 1 { p >>= 1; ret = (self.op)(ret, self.tree[p]); } ret } fn apply(&mut self, l: usize, r: usize, val: T) { let mut il = l + self.size; let mut ir = r + self.size; while il < ir { if il & 1 == 1 { self.tree[il] = (self.op)(self.tree[il], val); il += 1; } if ir & 1 == 1 { ir -= 1; self.tree[ir] = (self.op)(self.tree[ir], val); } il >>= 1; ir >>= 1; } } } } { let mut stree = Segmenttree::new(100_010, |x, y| x + y, 0.0); for i in 0..100_010 { stree.insert(i, point[i]); } let mut ans = vec![0.0; N]; for (i, s, t) in IST { let dv = stree.get(s, t); ans[i] += dv; } writeln!( out, "{}", ans.iter() .map(|x| x.to_string()) .collect::<Vec<_>>() .join("\n") ); #[derive(Clone)] struct Segmenttree<T> { len: usize, tree: Vec<T>, op: fn(T, T) -> T, id: T, } impl<T: Clone + Copy> Segmenttree<T> { /// 新規生成 fn new(l: usize, op: fn(T, T) -> T, id: T) -> Self { return Segmenttree { len: l, tree: vec![id; l * 2], op: op, id: id, }; } /// p 番目の要素を v に更新する. fn insert(&mut self, p: usize, v: T) { let mut pos = p; pos += self.len; self.tree[pos] = v; while pos > 1 { pos >>= 1; self.tree[pos] = (self.op)(self.tree[pos << 1], self.tree[pos << 1 | 1]); } } /// p 番目の要素を取得する. fn get_point(&self, p: usize) -> T { return self.tree[p + self.len]; } /// [l, r) の要素の総積を取得する. fn get(&self, l: usize, r: usize) -> T { let (mut pl, mut pr) = (l + self.len, r + self.len); let (mut vl, mut vr) = (self.id, self.id); while pl < pr { if pl & 1 == 1 { vl = (self.op)(vl, self.tree[pl]); pl += 1; } if pr & 1 == 1 { pr -= 1; vr = (self.op)(self.tree[pr], vr); } pl >>= 1; pr >>= 1; } (self.op)(vl, vr) } } } } struct Scanner<R> { reader: R, buf_str: Vec<u8>, buf_iter: str::SplitWhitespace<'static>, } impl<R: BufRead> Scanner<R> { fn new(reader: R) -> Self { Self { reader, buf_str: vec![], buf_iter: "".split_whitespace(), } } fn token<T: str::FromStr>(&mut self) -> T { loop { if let Some(token) = self.buf_iter.next() { return token.parse().ok().expect("Failed parse"); } self.buf_str.clear(); self.reader .read_until(b'\n', &mut self.buf_str) .expect("Failed read"); self.buf_iter = unsafe { let slice = str::from_utf8_unchecked(&self.buf_str); std::mem::transmute(slice.split_whitespace()) } } } }