結果

問題 No.924 紲星
ユーザー akakimidoriakakimidori
提出日時 2019-11-09 02:02:19
言語 Rust
(1.77.0 + proconio)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,989 bytes
コンパイル時間 14,284 ms
コンパイル使用メモリ 378,044 KB
実行使用メモリ 249,640 KB
最終ジャッジ日時 2024-09-15 03:50:32
合計ジャッジ時間 45,877 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 AC 1,524 ms
85,428 KB
testcase_14 AC 1,247 ms
53,344 KB
testcase_15 AC 1,280 ms
67,844 KB
testcase_16 AC 1,745 ms
211,812 KB
testcase_17 AC 2,270 ms
87,728 KB
testcase_18 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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(mut 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,
        }));
    }
    if t.is_none() {
        t = new_node(None, None);
    }
    let t = t.unwrap();
    let m = (l + r) / 2;
    let (left, right) = if x < m {
        (update(t.left.clone(), l, m, x, val), t.right.clone())
    } else {
        (t.left.clone(), update(t.right.clone(), 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();
//        writeln!(out, "{} {} {}", s, c, b[ok - 1].1).ok();
    }
}

fn main() {
    run();
}
0