結果

問題 No.1074 増殖
ユーザー akakimidoriakakimidori
提出日時 2020-06-05 22:06:38
言語 Rust
(1.77.0 + proconio)
結果
WA  
実行時間 -
コード長 8,408 bytes
コンパイル時間 16,453 ms
コンパイル使用メモリ 379,288 KB
実行使用メモリ 21,888 KB
最終ジャッジ日時 2024-05-09 21:23:20
合計ジャッジ時間 18,028 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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();
}
0