結果
| 問題 | No.3507 RangeSum RangeUpdate RangeSqrt |
| コンテスト | |
| ユーザー |
 titia
|
| 提出日時 | 2026-06-17 08:12:47 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,118 bytes |
| 記録 | |
| コンパイル時間 | 1,070 ms |
| コンパイル使用メモリ | 196,024 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-06-17 08:13:24 |
| 合計ジャッジ時間 | 7,288 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | AC * 12 TLE * 1 -- * 17 |
ソースコード
use std::io::{self, Read};
fn main() {
let mut input = String::new();
io::stdin().read_to_string(&mut input).unwrap();
let mut it = input.split_whitespace();
let n: usize = it.next().unwrap().parse().unwrap();
let q: usize = it.next().unwrap().parse().unwrap();
let mut a: Vec<i64> = (0..n)
.map(|_| it.next().unwrap().parse().unwrap())
.collect();
let sq = (n as f64).sqrt() as usize;
let len = (n + sq - 1) / sq;
let mut unit = vec![-1i64; len];
let mut sum = vec![0i64; len];
for b in 0..len {
let mut one: i64 = -1;
let l = b * sq;
let r = std::cmp::min(n, l + sq);
for j in l..r {
if one == -1 {
one = a[j];
} else if one == a[j] {
} else {
one = -2;
}
sum[b] += a[j];
}
if one >= 0 {
unit[b] = one;
}
}
let mut answers = Vec::<i64>::new();
for _ in 0..q {
let typ: i32 = it.next().unwrap().parse().unwrap();
if typ == 0 {
let l: usize = it.next().unwrap().parse().unwrap();
let r: usize = it.next().unwrap().parse().unwrap();
let mut ans = 0i64;
let mut now = l;
while now < r && now % sq != 0 {
if unit[now / sq] != -1 {
ans += unit[now / sq];
} else {
ans += a[now];
}
now += 1;
}
while now < r && now + sq < r {
ans += sum[now / sq];
now += sq;
}
while now < r {
if unit[now / sq] != -1 {
ans += unit[now / sq];
} else {
ans += a[now];
}
now += 1;
}
answers.push(ans);
} else if typ == 1 {
let l: usize = it.next().unwrap().parse().unwrap();
let r: usize = it.next().unwrap().parse().unwrap();
let x: i64 = it.next().unwrap().parse().unwrap();
let mut now = l;
while now < r && now % sq != 0 {
let b = now / sq;
if unit[b] != -1 {
let ume = unit[b];
unit[b] = -1;
sum[b] = 0;
let bl = b * sq;
let br = std::cmp::min(n, bl + sq);
for i in bl..br {
a[i] = ume;
sum[b] += a[i];
}
}
sum[b] -= a[now];
a[now] = x;
sum[b] += a[now];
now += 1;
}
while now < r && now + sq < r {
let b = now / sq;
unit[b] = x;
sum[b] = x * sq as i64;
now += sq;
}
while now < r {
let b = now / sq;
if unit[b] != -1 {
let ume = unit[b];
unit[b] = -1;
sum[b] = 0;
let bl = b * sq;
let br = std::cmp::min(n, bl + sq);
for i in bl..br {
a[i] = ume;
sum[b] += a[i];
}
}
sum[b] -= a[now];
a[now] = x;
sum[b] += a[now];
now += 1;
}
} else {
let l: usize = it.next().unwrap().parse().unwrap();
let r: usize = it.next().unwrap().parse().unwrap();
let mut now = l;
while now < r && now % sq != 0 {
let b = now / sq;
if unit[b] != -1 {
let ume = unit[b];
unit[b] = -1;
sum[b] = 0;
let bl = b * sq;
let br = std::cmp::min(n, bl + sq);
for i in bl..br {
a[i] = ume;
sum[b] += a[i];
}
}
sum[b] -= a[now];
a[now] = (a[now] as f64).sqrt() as i64;
sum[b] += a[now];
now += 1;
}
while now < r && now + sq < r {
let b = now / sq;
if unit[b] != -1 {
let ume = (unit[b] as f64).sqrt() as i64;
unit[b] = ume;
sum[b] = ume * sq as i64;
now += sq;
} else {
let mut one = -1i64;
sum[b] = 0;
for i in now..now + sq {
a[i] = (a[i] as f64).sqrt() as i64;
sum[b] += a[i];
if one == -1 {
one = a[i];
} else if one == a[i] {
} else {
one = -2;
}
}
if one >= 0 {
unit[b] = one;
sum[b] = one * sq as i64;
}
now += sq;
}
}
while now < r {
let b = now / sq;
if unit[b] != -1 {
let ume = unit[b];
unit[b] = -1;
sum[b] = 0;
let bl = b * sq;
let br = std::cmp::min(n, bl + sq);
for i in bl..br {
a[i] = ume;
sum[b] += a[i];
}
}
sum[b] -= a[now];
a[now] = (a[now] as f64).sqrt() as i64;
sum[b] += a[now];
now += 1;
}
}
}
let mut out = String::new();
for v in answers {
out.push_str(&format!("{}\n", v));
}
print!("{}", out);
}