結果
| 問題 | No.1074 増殖 |
| ユーザー |
 akakimidori
|
| 提出日時 | 2020-06-05 22:06:38 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,408 bytes |
| コンパイル時間 | 12,921 ms |
| コンパイル使用メモリ | 401,592 KB |
| 実行使用メモリ | 21,796 KB |
| 最終ジャッジ日時 | 2024-12-17 15:18:18 |
| 合計ジャッジ時間 | 15,263 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 3 |
| other | WA * 12 |
ソースコード
use std::cmp::*;use std::io::Read;use std::io::Write;const BOUND: i64 = 1_000_000_000_000;const INF: i64 = BOUND * 200_000 + 1;struct MaxCntSecond {max: i64,max_cnt: i64,second_max: i64,}impl MaxCntSecond {fn new(max: i64, max_cnt: i64, second_max: i64) -> Self {assert!(max_cnt > 0);assert!(max > second_max);MaxCntSecond {max: max,max_cnt: max_cnt,second_max: second_max,}}fn fold(&self, rhs: &Self) -> Self {match self.max.cmp(&rhs.max) {Ordering::Equal => MaxCntSecond::new(self.max,self.max_cnt + rhs.max_cnt,max(self.second_max, rhs.second_max),),Ordering::Less => {MaxCntSecond::new(rhs.max, rhs.max_cnt, max(self.max, rhs.second_max))}Ordering::Greater => {MaxCntSecond::new(self.max, self.max_cnt, max(self.second_max, rhs.max))}}}fn tag(&self, val: i64) -> bool {self.second_max < val && val < self.max}fn chmin(&mut self, val: i64) -> i64 {assert!(self.tag(val));let diff = val - self.max;self.max = val;diff * self.max_cnt}fn add(&mut self, val: i64) {self.max += val;self.second_max += val;}fn update(&mut self, val: i64) {assert!(self.second_max < -BOUND);self.max = val;self.second_max = -INF;}fn parts(&self) -> (i64, i64, i64) {(self.max, self.max_cnt, self.second_max)}}struct MinCntSecond {min: i64,min_cnt: i64,second_min: i64,}impl MinCntSecond {fn new(min: i64, min_cnt: i64, second_min: i64) -> Self {assert!(min_cnt > 0);assert!(min < second_min);MinCntSecond {min: min,min_cnt: min_cnt,second_min: second_min,}}fn fold(&self, rhs: &Self) -> Self {match self.min.cmp(&rhs.min) {Ordering::Equal => MinCntSecond::new(self.min,self.min_cnt + rhs.min_cnt,min(self.second_min, rhs.second_min),),Ordering::Greater => {MinCntSecond::new(rhs.min, rhs.min_cnt, min(self.min, rhs.second_min))}Ordering::Less => {MinCntSecond::new(self.min, self.min_cnt, min(self.second_min, rhs.min))}}}fn tag(&self, val: i64) -> bool {self.second_min > val && val > self.min}fn chmax(&mut self, val: i64) -> i64 {assert!(self.tag(val));let diff = val - self.min;self.min = val;diff * self.min_cnt}fn add(&mut self, val: i64) {self.min += val;self.second_min += val;}fn update(&mut self, val: i64) {assert!(self.second_min > BOUND);self.min = val;self.second_min = INF;}fn parts(&self) -> (i64, i64, i64) {(self.min, self.min_cnt, self.second_min)}}struct Value {max: MaxCntSecond,min: MinCntSecond,sum: i64,add: i64,len: i64,}impl Value {fn new(val: i64) -> Self {Value {max: MaxCntSecond::new(val, 1, -INF),min: MinCntSecond::new(val, 1, INF),sum: val,add: 0,len: 1,}}fn get_sum(&self) -> i64 {self.sum}fn get_max(&self) -> i64 {self.max.max}fn get_min(&self) -> i64 {self.min.min}fn fold(&self, rhs: &Self) -> Self {let max = self.max.fold(&rhs.max);let min = self.min.fold(&rhs.min);assert!(max.max >= min.min);let sum = self.get_sum() + rhs.get_sum();let len = self.len + rhs.len;Value {max: max,min: min,sum: sum,add: 0,len: len,}}fn tag_max(&self, val: i64) -> bool {self.max.tag(val)}fn tag_min(&self, val: i64) -> bool {self.min.tag(val)}fn chmin(&mut self, x: i64) {assert!(self.tag_max(x));let (a, _, _) = self.max.parts();let (p, _, r) = self.min.parts();self.sum += self.max.chmin(x);if a == p {self.min.update(x);} else if r == a {self.min.second_min = x;}}fn chmax(&mut self, x: i64) {assert!(self.tag_min(x));let (a, _, _) = self.max.parts();let (p, _, r) = self.min.parts();self.sum += self.min.chmax(x);if a == p {self.max.update(x);} else if r == a {self.max.second_max = x;}}fn add(&mut self, val: i64) {self.max.add(val);self.min.add(val);self.sum += val * self.len;self.add += val;}}fn propagate(seg: &mut [Value], k: usize) {let v = seg[k].add;seg[k].add = 0;let max = seg[k].get_max();let min = seg[k].get_min();for s in seg[(2 * k)..].iter_mut().take(2) {s.add(v);if s.tag_max(max) {s.chmin(max);}if s.tag_min(min) {s.chmax(min);}}}fn update(seg: &mut [Value], k: usize) {assert!(seg[k].add == 0);seg[k] = seg[2 * k].fold(&seg[2 * k + 1]);}#[allow(dead_code)]fn update_chmin(seg: &mut [Value], k: usize, l: usize, r: usize, x: usize, y: usize, val: i64) {if y <= l || r <= x || seg[k].get_max() <= val {return;}if x <= l && r <= y && seg[k].tag_max(val) {seg[k].chmin(val);return;}propagate(seg, k);let m = (l + r) / 2;update_chmin(seg, 2 * k, l, m, x, y, val);update_chmin(seg, 2 * k + 1, m, r, x, y, val);update(seg, k);}fn update_chmax(seg: &mut [Value], k: usize, l: usize, r: usize, x: usize, y: usize, val: i64) {if y <= l || r <= x || seg[k].get_min() >= val {return;}if x <= l && r <= y && seg[k].tag_min(val) {seg[k].chmax(val);return;}propagate(seg, k);let m = (l + r) / 2;update_chmax(seg, 2 * k, l, m, x, y, val);update_chmax(seg, 2 * k + 1, m, r, x, y, val);update(seg, k);}#[allow(dead_code)]fn update_add(seg: &mut [Value], k: usize, l: usize, r: usize, x: usize, y: usize, val: i64) {if y <= l || r <= x {return;}if x <= l && r <= y {seg[k].add(val);return;}propagate(seg, k);let m = (l + r) / 2;update_add(seg, 2 * k, l, m, x, y, val);update_add(seg, 2 * k + 1, m, r, x, y, val);update(seg, k);}fn find_sum(seg: &mut [Value], k: usize, l: usize, r: usize, x: usize, y: usize) -> i64 {if y <= l || r <= x {return 0;}if x <= l && r <= y {return seg[k].get_sum();}propagate(seg, k);let m = (l + r) / 2;find_sum(seg, 2 * k, l, m, x, y) + find_sum(seg, 2 * k + 1, m, r, x, y)}fn run() {let out = std::io::stdout();let mut out = std::io::BufWriter::new(out.lock());let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();let mut it = s.trim().split_whitespace();let n: usize = it.next().unwrap().parse().unwrap();let w: usize = 20000 + 1;let size = w.next_power_of_two();let mut seg = vec![];for _ in 0..4 {let mut a = (0..(2 * size)).map(|_| Value::new(0)).collect::<Vec<_>>();for i in (1..size).rev() {update(&mut a, i);}seg.push(a);}let mut ans = vec![0; n];for ans in ans.iter_mut() {let mut a = vec![];for _ in 0..4 {let v: i32 = it.next().unwrap().parse().unwrap();a.push(v);}for (seg, &(x, y)) in seg.iter_mut().zip(vec![(-a[0], -a[1]), (-a[0], a[3]), (a[2], -a[1]), (a[2], a[3])].iter()) {let x = x as usize;let y = y as i64;update_chmax(seg, 1, 0, size, 0, x, y);*ans += find_sum(seg, 1, 0, size, 0, size);}println!();}writeln!(out, "{}", ans[0]).ok();for ans in ans.windows(2) {let a = ans[1] - ans[0];writeln!(out, "{}", a).ok();}}fn main() {run();}