結果

問題 No.878 Range High-Element Query
コンテスト
ユーザー LyricalMaestro
提出日時 2024-08-18 21:18:30
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 4,517 bytes
コンパイル時間 13,690 ms
コンパイル使用メモリ 400,760 KB
実行使用メモリ 96,664 KB
最終ジャッジ日時 2024-08-18 21:18:49
合計ジャッジ時間 18,059 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `a`
   --> src/main.rs:109:17
    |
109 |             let a = A[j];
    |                 ^ help: if this is intentional, prefix it with an underscore: `_a`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: variable `L` should have a snake case name
  --> src/main.rs:44:17
   |
44 |         let mut L = self.size + l;
   |                 ^ help: convert the identifier to snake case: `l`
   |
   = note: `#[warn(non_snake_case)]` on by default

warning: variable `R` should have a snake case name
  --> src/main.rs:45:17
   |
45 |         let mut R = self.size + r;
   |                 ^ help: convert the identifier to snake case: `r`

warning: variable `N` should have a snake case name
  --> src/main.rs:69:9
   |
69 |     let N: usize = parts.next().unwrap().parse().unwrap();
   |         ^ help: convert the identifier to snake case: `n`

warning: variable `Q` should have a snake case name
  --> src/main.rs:70:9
   |
70 |     let Q: usize = parts.next().unwrap().parse().unwrap();
   |         ^ help: convert the identifier to snake case: `q`

warning: variable `A` should have a snake case name
  --> src/main.rs:73:9
   |
73 |     let A: Vec<i32> = second_line
   |         ^ help: convert the identifier to snake case: `a`

ソースコード

diff # 

use std::cmp::max;
use std::io::{self, BufRead};

struct SegmentTree {
    size: usize,
    array: Vec<i32>,
}

impl SegmentTree {
    fn new(init_array: Vec<i32>) -> SegmentTree {
        let mut n = 1;
        while n < init_array.len() {
            n *= 2;
        }

        let mut array = vec![-1; 2 * n];
        for (i, &a) in init_array.iter().enumerate() {
            array[n + i] = a;
        }

        let mut end_index = n;
        let mut start_index = end_index / 2;
        while start_index >= 1 {
            for i in start_index..end_index {
                array[i] = max(array[2 * i], array[2 * i + 1]);
            }
            end_index = start_index;
            start_index /= 2;
        }

        SegmentTree { size: n, array }
    }

    fn set(&mut self, x: usize, a: i32) {
        let mut index = self.size + x;
        self.array[index] = a;
        while index > 1 {
            index /= 2;
            self.array[index] = max(self.array[2 * index], self.array[2 * index + 1]);
        }
    }

    fn get_max(&self, l: usize, r: usize) -> i32 {
        let mut L = self.size + l;
        let mut R = self.size + r;

        let mut s = -1;
        while L < R {
            if R & 1 == 1 {
                R -= 1;
                s = max(s, self.array[R]);
            }
            if L & 1 == 1 {
                s = max(s, self.array[L]);
                L += 1;
            }
            L >>= 1;
            R >>= 1;
        }
        s
    }
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let first_line = lines.next().unwrap().unwrap();
    let mut parts = first_line.split_whitespace();
    let N: usize = parts.next().unwrap().parse().unwrap();
    let Q: usize = parts.next().unwrap().parse().unwrap();
    
    let second_line = lines.next().unwrap().unwrap();
    let A: Vec<i32> = second_line
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();
    
    let mut queries = Vec::new();
    for _ in 0..Q {
        let query_line = lines.next().unwrap().unwrap();
        let mut query_parts = query_line.split_whitespace();
        query_parts.next(); // skip the first number
        let l: usize = query_parts.next().unwrap().parse().unwrap();
        let r: usize = query_parts.next().unwrap().parse().unwrap();
        queries.push((l - 1, r - 1));
    }
    
    let mut seg_tree = SegmentTree::new(vec![-1; N + 1]);
    let mut max_left_list = vec![-1; N];
    for i in 0..N {
        let a = A[i];
        let ans = seg_tree.get_max((a + 1) as usize, N + 1);
        max_left_list[i] = ans;
        seg_tree.set(a as usize, i as i32);
    }

    let sqrt_n = (N as f64).sqrt() as usize;
    let mut partitions = Vec::new();
    let mut left = 0;
    while left < N {
        partitions.push((left, std::cmp::min(N, left + sqrt_n)));
        left += sqrt_n;
    }

    let mut partitions_array = Vec::new();
    for &(l, r) in &partitions {
        let mut cum_array = vec![0; N + 1];
        for j in l..r {
            let a = A[j];
            let l_index = max_left_list[j];
            cum_array[(l_index + 1) as usize] += 1;
        }

        let mut cum_a = 0;
        for n in 0..=N {
            cum_a += cum_array[n];
            cum_array[n] = cum_a;
        }
        partitions_array.push(cum_array);
    }

    for &(l, r) in &queries {
        let mut left_i = -1;
        let mut right_i = -1;
        for i in 0..partitions.len() {
            if l < partitions[i].1 {
                left_i = i as i32;
            }
            if r < partitions[i].1 {
                right_i = i as i32;
            }
        }

        let mut answer = 0;
        if (right_i - left_i).abs() <= 1 {
            for i in l..=r {
                if l as i32 > max_left_list[i] as i32 {
                    answer += 1;
                }
            }
        } else {
            for i in l..partitions[left_i as usize].1 {
                if l as i32 > max_left_list[i] as i32 {
                    answer += 1;
                }
            }
            for i in partitions[right_i as usize].0..=r {
                if l as i32 > max_left_list[i] as i32 {
                    answer += 1;
                }
            }
            for i in (left_i + 1) as usize..right_i as usize {
                let a = partitions_array[i][l + 1];
                answer += partitions_array[i][1] - partitions_array[i][0] - a;
            }
        }
        println!("{}", answer);
    }
}
0