結果

問題 No.8121 [Deleted]
ユーザー AwashAmityOak
提出日時 2025-04-01 22:32:34
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 1,325 bytes
コンパイル時間 14,164 ms
コンパイル使用メモリ 383,920 KB
実行使用メモリ 18,592 KB
最終ジャッジ日時 2025-04-01 22:32:56
合計ジャッジ時間 17,985 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

struct Segtree {
	n: usize,
	data: Vec<i64>,
}

impl Segtree {
	fn new(a: Vec<i64>) -> Self {
		let mut bit_ceil = 1;
		while bit_ceil < a.len() {
			bit_ceil <<= 1;
		}
		
		let mut data = vec![i64::MIN; bit_ceil * 2];
		for i in 0..a.len() {
			data[bit_ceil + i] = a[i];
		}
		for i in (0..bit_ceil).rev() {
			data[i] = data[i*2].max(data[i*2+1]);
		}
		Self {
			n: bit_ceil,
			data,
		}
	}
	fn get(&self, i: usize) -> i64 {
		self.data[self.n + i]
	}
	fn set(&mut self, i: usize, x: i64) {
		let mut i = self.n + i;
		self.data[i] = x;
		while 1 < i {
			i >>= 1;
			self.data[i] = self.data[i*2].max(self.data[i*2+1]);
		}
	}
	fn prod(&self, l: usize, r: usize) -> i64 {
		let mut l = self.n + l;
		let mut r = self.n + r;
		
		let mut res = i64::MIN;
		while l < r {
			if l % 2 != 0 {
				res = res.max(self.data[l]);
				l += 1;
			}
			if r % 2 != 0 {
				r -= 1;
				res = res.max(self.data[r]);
			}
			l >>= 1;
			r >>= 1;
		}
		res
	}
}

fn main() {
	proconio::input! {
		n: usize,
		q: usize,
		a: [i64; n],
		queries: [(i64, i64, i64); q],
	}
	
	let mut tree = Segtree::new(a);
	for (t, a, b) in queries.into_iter() {
		if t == 1 {
			let a = a - 1;
			let x = tree.get(a as usize);
			tree.set(a as usize, x + b);
		} else {
			let a = a - 1;
			println!("{}", tree.prod(a as usize, b as usize));
		}
	}
}
0