結果
| 問題 |
No.1441 MErGe
|
| コンテスト | |
| ユーザー |
 Moss_Local
|
| 提出日時 | 2021-03-26 22:42:30 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,722 bytes |
| コンパイル時間 | 13,083 ms |
| コンパイル使用メモリ | 400,776 KB |
| 実行使用メモリ | 34,580 KB |
| 最終ジャッジ日時 | 2024-11-29 00:36:50 |
| 合計ジャッジ時間 | 49,709 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 WA * 1 |
| other | AC * 1 WA * 10 TLE * 17 |
コンパイルメッセージ
warning: unused variable: `x`
--> src/main.rs:307:10
|
307 | fn g(x: Self::Monoid, y: Self::OperatorMonoid, _: usize) -> Self::Monoid {
| ^ help: if this is intentional, prefix it with an underscore: `_x`
|
= note: `#[warn(unused_variables)]` on by default
warning: unused variable: `i`
--> src/main.rs:340:9
|
340 | for i in 0..q {
| ^ help: if this is intentional, prefix it with an underscore: `_i`
warning: variable does not need to be mutable
--> src/main.rs:330:9
|
330 | let mut vec: Vec<i64> = read_vec();
| ----^^^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` on by default
warning: variable does not need to be mutable
--> src/main.rs:358:13
|
358 | let mut l1 = ok;
| ----^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:376:13
|
376 | let mut r1 = ok;
| ----^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:380:17
|
380 | let mut res = acc[r1 + 1] - acc[l1];
| ----^^^
| |
| help: remove this `mut`
ソースコード
// -*- coding:utf-8-unix -*-
// #![feature(map_first_last)]
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]
use std::collections::*;
use std::convert::*;
use std::convert::{From, Into};
use std::fmt::Debug;
use std::fs::File;
use std::io::prelude::*;
use std::io::*;
use std::marker::Copy;
use std::mem::*;
use std::ops::Bound::*;
use std::ops::{Add, Mul, Neg, Sub};
use std::str;
use std::vec;
use std::{cmp, process::Output};
use std::{cmp::Ordering, env::consts::DLL_PREFIX};
use std::{cmp::Ordering::*, f32::consts::PI};
const INF: i64 = 1223372036854775807;
const UINF: usize = INF as usize;
const FINF: f64 = 122337203685.0;
const INF128: i128 = 1223372036854775807000000000000;
const LINF: i64 = 2147483647;
// const MOD: i64 = 1000000007;
const MOD: i64 = 998244353;
const UMOD: usize = MOD as usize;
use std::cmp::*;
use std::collections::*;
use std::io::stdin;
use std::io::stdout;
use std::io::Write;
macro_rules! p {
($x:expr) => {
println!("{}", $x);
};
}
macro_rules! pp {
($x:expr) => {
println!("{:?}", $x);
};
}
macro_rules! d {
($x:expr) => {
dbg!($x);
};
}
// use str::Chars;
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
let mut s = String::new();
std::io::stdin().read_line(&mut s).ok();
s.trim().parse().ok().unwrap()
}
// #[allow(dead_code)]
// fn readi() -> (i64) {
// let mut str = String::new();
// let _ = stdin().read_line(&mut str).unwrap();
// let mut iter = str.split_whitespace();
// iter.next().unwrap().parse::<i64>().unwrap()
// }
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
read::<String>()
.split_whitespace()
.map(|e| e.parse().ok().unwrap())
.collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
(0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn readii() -> (i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
fn readff() -> (f64, f64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<f64>().unwrap(),
iter.next().unwrap().parse::<f64>().unwrap(),
)
}
#[allow(dead_code)]
fn readiii() -> (i64, i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
#[allow(dead_code)]
fn readuu() -> (usize, usize) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
}
fn readcc() -> (char, char) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<char>().unwrap(),
iter.next().unwrap().parse::<char>().unwrap(),
)
}
#[allow(dead_code)]
fn readuuu() -> (usize, usize, usize) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
}
#[allow(dead_code)]
fn readuuuu() -> (usize, usize, usize, usize) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
}
fn readiiii() -> (i64, i64, i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
// / Equivalent to std::lowerbound and std::upperbound in c++
fn neighbors(tree: &BTreeSet<i64>, val: i64) -> (Option<&i64>, Option<&i64>) {
use std::ops::Bound::*;
let mut before = tree.range((Unbounded, Excluded(val)));
let mut after = tree.range((Excluded(val), Unbounded));
(before.next_back(), after.next())
}
trait SEGLazyImpl {
type Monoid: Copy;
type OperatorMonoid: Copy + PartialEq;
fn m0() -> Self::Monoid;
fn om0() -> Self::OperatorMonoid;
fn f(x: Self::Monoid, y: Self::Monoid) -> Self::Monoid;
fn g(x: Self::Monoid, y: Self::OperatorMonoid, weight: usize) -> Self::Monoid;
fn h(x: Self::OperatorMonoid, y: Self::OperatorMonoid) -> Self::OperatorMonoid;
}
struct SEGLazy<T: SEGLazyImpl> {
n: usize,
data: Vec<T::Monoid>,
lazy: Vec<T::OperatorMonoid>,
weight: Vec<usize>,
}
impl<T: SEGLazyImpl> SEGLazy<T> {
pub fn new(n: usize, init: T::Monoid) -> SEGLazy<T> {
let weights = vec![1; n];
Self::with_weight(n, init, weights)
}
pub fn with_weight(n: usize, init: T::Monoid, weights: Vec<usize>) -> Self {
let mut m = 1;
while m < n {
m *= 2;
}
SEGLazy {
n: m,
data: vec![init; m * 2],
lazy: vec![T::om0(); m * 2],
weight: Self::mk_weight(&weights),
}
}
fn mk_weight(xs: &[usize]) -> Vec<usize> {
let n = xs.len();
let mut m = 1;
while m < n {
m *= 2;
}
let mut res = vec![0; 2 * m];
for i in 0..n {
res[m + i] = xs[i];
}
for k in (1..m).rev() {
let l = 2 * k;
let r = 2 * k + 1;
res[k] = res[l] + res[r];
}
res
}
fn propagate(&mut self, k: usize) {
let weight = self.weight[k];
if self.lazy[k] != T::om0() {
if k < self.n {
self.lazy[2 * k + 0] = T::h(self.lazy[2 * k + 0], self.lazy[k]);
self.lazy[2 * k + 1] = T::h(self.lazy[2 * k + 1], self.lazy[k]);
}
self.data[k] = T::g(self.data[k], self.lazy[k], weight);
self.lazy[k] = T::om0();
}
}
fn do_update(
&mut self,
a: usize,
b: usize,
x: T::OperatorMonoid,
k: usize,
l: usize,
r: usize,
) -> T::Monoid {
self.propagate(k);
if r <= a || b <= l {
self.data[k]
} else if a <= l && r <= b {
self.lazy[k] = T::h(self.lazy[k], x);
self.propagate(k);
self.data[k]
} else {
self.data[k] = T::f(
self.do_update(a, b, x, 2 * k + 0, l, (l + r) >> 1),
self.do_update(a, b, x, 2 * k + 1, (l + r) >> 1, r),
);
self.data[k]
}
}
#[doc = "[l,r)"]
pub fn update(&mut self, l: usize, r: usize, x: T::OperatorMonoid) -> T::Monoid {
let n = self.n;
self.do_update(l, r, x, 1, 0, n)
}
fn do_query(&mut self, a: usize, b: usize, k: usize, l: usize, r: usize) -> T::Monoid {
self.propagate(k);
if r <= a || b <= l {
T::m0()
} else if a <= l && r <= b {
self.data[k]
} else {
T::f(
self.do_query(a, b, 2 * k + 0, l, (l + r) >> 1),
self.do_query(a, b, 2 * k + 1, (l + r) >> 1, r),
)
}
}
#[doc = "[l,r)"]
pub fn query(&mut self, l: usize, r: usize) -> T::Monoid {
let n = self.n;
self.do_query(l, r, 1, 0, n)
}
}
struct RUQ;
impl SEGLazyImpl for RUQ {
type Monoid = i64;
type OperatorMonoid = i64;
fn m0() -> Self::Monoid {
0
}
fn om0() -> Self::OperatorMonoid {
0
}
fn f(x: Self::Monoid, y: Self::Monoid) -> Self::Monoid {
x + y
}
fn g(x: Self::Monoid, y: Self::OperatorMonoid, _: usize) -> Self::Monoid {
max(0, y)
}
fn h(x: Self::OperatorMonoid, y: Self::OperatorMonoid) -> Self::OperatorMonoid {
x + y
}
}
// #[test]
// fn test_MAX_RUQ() {
// let mut seg: SEGLazy<MAX_RUQ> = SEGLazy::new(10, MAX_RUQ::m0());
// assert_eq!(seg.query(0, 3), 0);
// seg.update(0, 2, 10); // [10,10,0,...]
// assert_eq!(seg.query(0, 3), 10);
// assert_eq!(seg.query(2, 3), 0);
// seg.update(1, 5, 20);
// assert_eq!(seg.query(0, 3), 20);
// assert_eq!(seg.query(0, 1), 10);
// seg.update(0, 1, 5);
// assert_eq!(seg.query(0, 1), 5);
// }
fn solve() {
let (n, q) = readuu();
let mut vec: Vec<i64> = read_vec();
let mut acc = vec![0; n + 1];
for i in 0..n {
acc[i + 1] = acc[i] + vec[i];
}
let mut seg: SEGLazy<RUQ> = SEGLazy::new(202020, 0);
for i in 0..202020 {
seg.update(i, i + 1, 1);
}
for i in 0..q {
let (t, l, r) = readuuu();
let mut f = |x: usize| -> bool {
return seg.query(0, x) < l as i64;
};
let mut ok = 0;
let mut ng = n;
while (ng - ok) > 1 {
let mid = (ok + ng) / 2;
if f(mid) {
ok = mid;
} else {
ng = mid;
}
}
let mut l1 = ok;
let mut f2 = |x: usize| -> bool {
return seg.query(0, x) < r as i64;
};
let mut ok = 0;
let mut ng = n + 1;
while (ng - ok) > 1 {
let mid = (ok + ng) / 2;
if f2(mid) {
ok = mid;
} else {
ng = mid;
}
}
let mut r1 = ok;
if t == 1 {
seg.update(l1, r1, -1);
} else {
let mut res = acc[r1 + 1] - acc[l1];
println!("{:?}", res);
// pp!((l1, r1));
// for i in 0..n {
// print!("{} ", seg.query(0, i + 1));
// }
// p!("");
// for i in 0..n {
// print!("{} ", i);
// }
// p!("");
}
}
return;
}
fn main() {
solve()
}