結果

問題 No.877 Range ReLU Query
ユーザー akakimidoriakakimidori
提出日時 2019-09-06 22:25:17
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 74 ms / 2,000 ms
コード長 3,705 bytes
コンパイル時間 15,314 ms
コンパイル使用メモリ 376,960 KB
実行使用メモリ 15,792 KB
最終ジャッジ日時 2024-11-08 10:07:37
合計ジャッジ時間 17,804 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 1 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 1 ms
5,248 KB
testcase_08 AC 1 ms
5,248 KB
testcase_09 AC 1 ms
5,248 KB
testcase_10 AC 1 ms
5,248 KB
testcase_11 AC 69 ms
14,964 KB
testcase_12 AC 62 ms
13,408 KB
testcase_13 AC 49 ms
11,304 KB
testcase_14 AC 50 ms
11,688 KB
testcase_15 AC 74 ms
15,668 KB
testcase_16 AC 70 ms
14,968 KB
testcase_17 AC 72 ms
15,332 KB
testcase_18 AC 72 ms
15,352 KB
testcase_19 AC 68 ms
15,792 KB
testcase_20 AC 72 ms
15,684 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 1-indexedなBIT
// 座標xへの加算、[1,x]の和, ([1,x]の和)>=s となる最小のxの探索
// ---------- begin fenwick tree ----------
#[allow(dead_code)]
mod fenwick {
    type T = i64;
    const ZERO: T = 0;
    pub struct Tree {
        a: Vec<T>,
    }
    impl Tree {
        pub fn new(n: usize) -> Tree {
            Tree {
                a: vec![ZERO; n + 1],
            }
        }
        pub fn add(&mut self, mut x: usize, v: T) {
            while x < self.a.len() {
                self.a[x] += v;
                x += x & (!x + 1);
            }
        }
        pub fn sum(&self, mut x: usize) -> T {
            debug_assert!(x < self.a.len());
            let mut res = ZERO;
            while x > 0 {
                res += self.a[x];
                x -= x & (!x + 1);
            }
            res
        }
        pub fn search(&self, s: T) -> usize {
            debug_assert!(self.sum(self.a.len() - 1) >= s);
            let mut k = 1;
            while 2 * k < self.a.len() {
                k *= 2;
            }
            let mut x = 0;
            let mut w = ZERO;
            while k > 0 {
                if k + x < self.a.len() && w + self.a[x + k] < s {
                    w += self.a[x + k];
                    x += k;
                }
                k >>= 1;
            }
            x + 1
        }
    }
}
// ---------- end fenwick tree ----------
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

// ここまで

use std::io::Write;

fn run() {
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    input! {
        n: usize,
        q: usize,
        a: [i64; n],
        p: [(u8, usize, usize, i64); q],
    }
    let mut ai = Vec::with_capacity(n);
    for (i, a) in a.iter().enumerate() {
        ai.push((*a, i + 1));
    }
    ai.sort();
    let a = ai;
    let mut b = Vec::with_capacity(q);
    for (i, &(_, l, r, x)) in p.iter().enumerate() {
        b.push((x, l, r, i));
    }
    b.sort();
    let mut ans = vec![0; q];
    let mut s = fenwick::Tree::new(n);
    let mut cnt = fenwick::Tree::new(n);
    let mut i = n;
    for &(x, l, r, k) in b.iter().rev() {
        while i > 0 && a[i - 1].0 > x {
            let (a, k) = a[i - 1];
            s.add(k, a);
            cnt.add(k, 1);
            i -= 1;
        }
        let v = s.sum(r) - s.sum(l - 1) - x * (cnt.sum(r) - cnt.sum(l - 1));
        ans[k] = v;
    }
    for v in ans {
        writeln!(out, "{}", v).unwrap();
    }
}

fn main() {
    run();
}
0