結果
問題 |
No.2170 Left Addition Machine
|
ユーザー |
![]() |
提出日時 | 2022-12-22 22:34:57 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 155 ms / 2,000 ms |
コード長 | 1,467 bytes |
コンパイル時間 | 12,777 ms |
コンパイル使用メモリ | 389,592 KB |
実行使用メモリ | 26,980 KB |
最終ジャッジ日時 | 2024-11-18 06:29:51 |
合計ジャッジ時間 | 24,981 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 69 |
ソースコード
use std::{fs, io, io::Write}; const MOD: i64 = 998244353; const HALF: i64 = (MOD + 1) / 2; fn main() { let s = fs::read_to_string("/dev/stdin").unwrap(); let v: Vec<_> = s.split_whitespace().collect(); let n: usize = v[0].trim().parse().unwrap(); let q: usize = v[1].trim().parse().unwrap(); let mut a: Vec<i64> = vec![0; n]; for i in 0..n { a[i] = v[i + 2].trim().parse().unwrap(); } let mut l: Vec<usize> = vec![0; q]; let mut r: Vec<usize> = vec![0; q]; for i in 0..q { l[i] = v[2 * i + n + 2].trim().parse().unwrap(); r[i] = v[2 * i + n + 3].trim().parse().unwrap(); } let mut last = vec![0; n]; for i in 1..n { if a[i] > a[i - 1] { last[i] = last[i - 1]; } else { last[i] = i; } } let mut a_sum = vec![0; n + 1]; let mut pow_half = vec![1; n + 1]; let mut mul: i64 = 1; for i in 0..n { a_sum[i + 1] = (a_sum[i] + mul * a[i]) % MOD; mul += mul; if mul >= MOD { mul -= MOD; } pow_half[i + 1] = pow_half[i] * HALF % MOD; } let mut out = io::BufWriter::new(io::stdout().lock()); for i in 0..q { l[i] -= 1; r[i] -= 1; l[i] = l[i].max(last[r[i]]); writeln!( out, "{}", ((a_sum[r[i] + 1] - a_sum[l[i] + 1] + MOD) * pow_half[l[i] + 1] + a[l[i]]) % MOD ) .unwrap(); } }