結果

問題 No.924 紲星
ユーザー akakimidoriakakimidori
提出日時 2020-02-08 01:32:21
言語 Rust
(1.77.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,924 bytes
コンパイル時間 2,292 ms
コンパイル使用メモリ 188,920 KB
実行使用メモリ 254,572 KB
最終ジャッジ日時 2023-10-26 00:33:18
合計ジャッジ時間 8,942 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 3 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 3 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 TLE -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::Read;
use std::io::Write;
use std::rc::Rc;

type Link = Option<Rc<Node>>;

struct Node {
    sum: i64,
    cnt: i64,
    left: Link,
    right: Link,
}

fn eval(t: &Link) -> (i64, i64) {
    match t.as_ref() {
        None => (0, 0),
        Some(ref t) => (t.sum, t.cnt),
    }
}

fn new_node(l: Link, r: Link) -> Link {
    let u = eval(&l);
    let v = eval(&r);
    Some(Rc::new(Node {
        sum: u.0 + v.0,
        cnt: u.1 + v.1,
        left: l,
        right: r,
    }))
}

fn find(t: &Link, l: usize, r: usize, x: usize, y: usize) -> (i64, i64) {
    if t.is_none() || r <= x || y <= l {
        return (0, 0);
    }
    let t = t.as_ref().unwrap();
    if x <= l && r <= y {
        return (t.sum, t.cnt);
    }
    let m = (l + r) / 2;
    let (a, b) = find(&t.left , l, m, x, y);
    let (c, d) = find(&t.right, m, r, x, y);
    (a + c, b + d)
}

fn update(t: Link, l: usize, r: usize, x: usize, val: i64) -> Link {
    assert!(l <= x && x < r);
    if l + 1 == r {
        return Some(Rc::new(Node {
            sum: val,
            cnt: 1,
            left: None,
            right: None,
        }));
    }
    let mut left = None;
    let mut right = None;
    if let Some(t) = t {
        left = t.left.clone();
        right = t.right.clone();
    }
    let m = (l + r) / 2;
    if x < m {
        left = update(left, l, m, x, val);
    } else {
        right = update(right, m, r, x, val);
    }
    new_node(left, right)
}

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 q: usize = it.next().unwrap().parse().unwrap();
    let a: Vec<i64> = (0..n).map(|_| it.next().unwrap().parse().unwrap()).collect();
    let mut b: Vec<(usize, i64)> = a.clone().into_iter().enumerate().collect();
    b.sort_by_key(|b| b.1);
    let mut seg = vec![None; n + 1];
    for i in 0..n {
        seg[i + 1] = update(seg[i].clone(), 0, n, b[i].0, b[i].1);
    }
    let mut sum = a.clone();
    sum.push(0);
    for i in (0..n).rev() {
        sum[i] += sum[i + 1];
    }
    for _ in 0..q {
        let l = it.next().unwrap().parse::<usize>().unwrap() - 1;
        let r = it.next().unwrap().parse::<usize>().unwrap();
        let len = (r - l) as i64;
        let mut ng = 0;
        let mut ok = n;
        while ok - ng > 1 {
            let mid = (ok + ng) / 2;
            let (_, c) = find(&seg[mid], 0, n, l, r);
            if 2 * c >= len {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        let (s, c) = find(&seg[ok], 0, n, l, r);
        let ans = (sum[l] - sum[r] - s - (len - c) * b[ok - 1].1) + (b[ok - 1].1 * c - s);
        writeln!(out, "{}", ans).ok();
    }
}

fn main() {
    run();
}
0