結果

問題 No.924 紲星
コンテスト
ユーザー akakimidori
提出日時 2020-02-08 01:32:21
言語 Rust
(1.83.0 + proconio)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,924 bytes
コンパイル時間 17,170 ms
コンパイル使用メモリ 377,472 KB
実行使用メモリ 249,640 KB
最終ジャッジ日時 2024-12-26 21:43:58
合計ジャッジ時間 47,610 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

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