#1150956 (Rust) No.3464 Max and Sum on Grid

• 問題: No.3464 Max and Sum on Grid
• ユーザー: LyricalMaestro
• 提出日時: 2026-03-01 23:28:29
• 言語: Rust (1.93.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 3,042 ms / 5,000 ms
• コード長: 5,748 bytes
• コンパイル時間: 7,347 ms
• コンパイル使用メモリ: 208,464 KB
• 実行使用メモリ: 52,648 KB
• 最終ジャッジ日時: 2026-03-01 23:29:13
• 合計ジャッジ時間: 28,887 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
sample	AC * 1
other	AC * 10

ソースコード

use proconio::input;
use std::cmp::min;

struct Calculator {
    a: Vec<i64>,
    b: Vec<i64>,
    sqrt_n: usize,
    cum_rect_values: Vec<Vec<i64>>,
    row_values: Vec<Vec<i64>>,
    col_values: Vec<Vec<i64>>,
}

impl Calculator {
    fn calculate(&self, row_index: i64, col_index: i64) -> i64 {
        if row_index < 0 || col_index < 0 {
            return 0;
        }

        let row_index = row_index as usize;
        let col_index = col_index as usize;

        let mut r_index = row_index / self.sqrt_n;
        let mut c_index = col_index / self.sqrt_n;

        r_index = min(r_index, self.sqrt_n);
        c_index = min(c_index, self.sqrt_n);

        let mut answer = self.cum_rect_values[r_index][c_index];

        for r in r_index * self.sqrt_n..=row_index {
            answer += self.row_values[r][c_index];
        }

        for c in c_index * self.sqrt_n..=col_index {
            answer += self.col_values[c][r_index];
        }

        let mut array: Vec<(i64, i32)> = vec![];

        for r in r_index * self.sqrt_n..=row_index {
            array.push((self.a[r], 0));
        }
        for c in c_index * self.sqrt_n..=col_index {
            array.push((self.b[c], 1));
        }

        array.sort_by(|x, y| y.0.cmp(&x.0));

        let mut r_rest = row_index + 1 - r_index * self.sqrt_n;
        let mut c_rest = col_index + 1 - c_index * self.sqrt_n;

        for (val, typ) in array {
            if typ == 0 {
                answer += val * c_rest as i64;
                r_rest -= 1;
            } else {
                answer += val * r_rest as i64;
                c_rest -= 1;
            }
        }

        answer
    }
}

fn prepare_cum_rect_values(
    sqrt_n: usize,
    array: &Vec<(i64, usize, i32)>,
) -> Vec<Vec<i64>> {
    let mut rect_values = vec![vec![0i64; sqrt_n]; sqrt_n];
    let mut row_rest_num = vec![vec![sqrt_n as i64; sqrt_n]; sqrt_n];
    let mut col_rest_num = vec![vec![sqrt_n as i64; sqrt_n]; sqrt_n];

    for &(a, index, data_type) in array {
        if index < sqrt_n * sqrt_n {
            if data_type == 0 {
                let row_index = index / sqrt_n;
                for c_index in 0..sqrt_n {
                    rect_values[row_index][c_index] +=
                        a * col_rest_num[row_index][c_index];
                    row_rest_num[row_index][c_index] -= 1;
                }
            } else {
                let col_index = index / sqrt_n;
                for r_index in 0..sqrt_n {
                    rect_values[r_index][col_index] +=
                        a * row_rest_num[r_index][col_index];
                    col_rest_num[r_index][col_index] -= 1;
                }
            }
        }
    }

    let mut cum_rect_values =
        vec![vec![0i64; sqrt_n + 1]; sqrt_n + 1];

    for i in 0..sqrt_n {
        let mut row_sum = 0;
        for j in 0..sqrt_n {
            row_sum += rect_values[i][j];
            cum_rect_values[i + 1][j + 1] =
                row_sum + cum_rect_values[i][j + 1];
        }
    }

    cum_rect_values
}

fn prepare_row_col_values(
    n: usize,
    sqrt_n: usize,
    array: &Vec<(i64, usize, i32)>,
) -> (Vec<Vec<i64>>, Vec<Vec<i64>>) {
    let mut row_values = vec![vec![0i64; sqrt_n + 1]; n];
    let mut col_values = vec![vec![0i64; sqrt_n + 1]; n];

    let mut row_m_values = vec![0i64; sqrt_n];
    let mut col_m_values = vec![0i64; sqrt_n];

    let mut row_rest_num = vec![sqrt_n as i64; sqrt_n];
    let mut col_rest_num = vec![sqrt_n as i64; sqrt_n];

    for &(a, index, data_type) in array {
        if data_type == 0 {
            for j in 0..sqrt_n {
                row_values[index][j + 1] +=
                    col_m_values[j] + a * col_rest_num[j];
            }

            if index < sqrt_n * sqrt_n {
                row_m_values[index / sqrt_n] += a;
                row_rest_num[index / sqrt_n] -= 1;
            }
        } else {
            for j in 0..sqrt_n {
                col_values[index][j + 1] +=
                    row_m_values[j] + a * row_rest_num[j];
            }

            if index < sqrt_n * sqrt_n {
                col_m_values[index / sqrt_n] += a;
                col_rest_num[index / sqrt_n] -= 1;
            }
        }
    }

    for i in 0..n {
        let mut x = 0;
        for j in 0..=sqrt_n {
            x += row_values[i][j];
            row_values[i][j] = x;
        }

        let mut y = 0;
        for j in 0..=sqrt_n {
            y += col_values[i][j];
            col_values[i][j] = y;
        }
    }

    (row_values, col_values)
}

fn main() {
    input! {
        n: usize,
        q: usize,
        a: [i64; n],
        b: [i64; n],
    }

    let mut queries = vec![];
    for _ in 0..q {
        input! {
            l: i64,
            d: i64,
            r: i64,
            u: i64,
        }
        queries.push((l - 1, d - 1, r - 1, u - 1));
    }

    let sqrt_n = (n as f64).sqrt() as usize;

    let mut array: Vec<(i64, usize, i32)> = vec![];

    for i in 0..n {
        array.push((a[i], i, 0));
        array.push((b[i], i, 1));
    }

    array.sort_by(|x, y| y.0.cmp(&x.0));

    let cum_rect_values =
        prepare_cum_rect_values(sqrt_n, &array);

    let (row_values, col_values) =
        prepare_row_col_values(n, sqrt_n, &array);

    let calculator = Calculator {
        a,
        b,
        sqrt_n,
        cum_rect_values,
        row_values,
        col_values,
    };

    for (l, d, r, u) in queries {
        let ans1 = calculator.calculate(r, u);
        let ans2 = calculator.calculate(r, d - 1);
        let ans3 = calculator.calculate(l - 1, u);
        let ans4 = calculator.calculate(l - 1, d - 1);

        let answer = ans1 - ans2 - ans3 + ans4;
        println!("{}", answer);
    }
}