#1172703 (Rust) No.2338 Range AtCoder Query

• 問題: No.2338 Range AtCoder Query
• ユーザー: LyricalMaestro
• 提出日時: 2026-07-24 01:50:06
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 1,225 ms / 4,000 ms
• コード長: 5,303 bytes
• コンパイル時間: 8,651 ms
• コンパイル使用メモリ: 196,160 KB
• 実行使用メモリ: 30,884 KB
• 最終ジャッジ日時: 2026-07-24 01:50:52
• 合計ジャッジ時間: 35,205 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

use proconio::{input, marker::Chars};
use std::collections::VecDeque;

#[derive(Clone, Copy)]
struct Query {
    block: usize,
    index: usize,
    left: usize,
    right: usize,
}

struct Interval {
    ac_count: i64,
    wa_count: i64,
    deques: Vec<VecDeque<i64>>,
    submissions: Vec<(usize, bool)>,
}

impl Interval {
    fn new(
        ac_count: i64,
        wa_count: i64,
        deques: Vec<VecDeque<i64>>,
        submissions: Vec<(usize, bool)>,
    ) -> Self {
        Self {
            ac_count,
            wa_count,
            deques,
            submissions,
        }
    }

    fn delete_from_left(&mut self, index: usize) {
        let (problem, is_ac) = self.submissions[index];
        let deque = &mut self.deques[problem];

        if !is_ac {
            *deque.front_mut().unwrap() -= 1;

            if deque.len() > 1 {
                self.wa_count -= 1;
            }
        } else {
            deque.pop_front();
            self.ac_count -= 1;

            if deque.len() > 1 {
                self.ac_count += 1;
                self.wa_count += deque[0];
            }
        }
    }

    fn add_from_left(&mut self, index: usize) {
        let (problem, is_ac) = self.submissions[index];
        let deque = &mut self.deques[problem];

        if !is_ac {
            *deque.front_mut().unwrap() += 1;

            if deque.len() > 1 {
                self.wa_count += 1;
            }
        } else {
            if deque.len() > 1 {
                self.wa_count -= deque[0];
                self.ac_count -= 1;
            }

            deque.push_front(0);
            self.ac_count += 1;
        }
    }

    fn delete_from_right(&mut self, index: usize) {
        let (problem, is_ac) = self.submissions[index];
        let deque = &mut self.deques[problem];

        if !is_ac {
            *deque.back_mut().unwrap() -= 1;
        } else {
            deque.pop_back();

            if deque.len() == 1 {
                self.wa_count -= deque[0];
                self.ac_count -= 1;
            }
        }
    }

    fn add_from_right(&mut self, index: usize) {
        let (problem, is_ac) = self.submissions[index];
        let deque = &mut self.deques[problem];

        if !is_ac {
            *deque.back_mut().unwrap() += 1;
        } else {
            if deque.len() == 1 {
                self.wa_count += deque[0];
                self.ac_count += 1;
            }

            deque.push_back(0);
        }
    }
}

fn main() {
    input! {
        n: usize,
        m: usize,
        q: usize,
    }

    let mut submissions = Vec::with_capacity(n);

    for _ in 0..n {
        input! {
            p: usize,
            s: Chars,
        }

        let is_ac = s.as_slice() == ['A', 'C'];
        submissions.push((p - 1, is_ac));
    }

    let block_size = (n as f64).sqrt() as usize;
    let block_size = block_size.max(1);

    let mut queries = Vec::with_capacity(q);

    for index in 0..q {
        input! {
            l: usize,
            r: usize,
        }

        let left = l - 1;
        let right = r - 1;

        queries.push(Query {
            block: left / block_size,
            index,
            left,
            right,
        });
    }

    /*
    Python版の意図に合わせて、

        block * (2 * N) - right

    の昇順で並べる。

    usizeでは負数を扱えないため、i64へ変換している。
    */
    queries.sort_by_key(|query| {
        query.block as i64 * (2 * n) as i64 - query.right as i64
    });

    /*
    最初は区間 [0, N - 1]、つまり全提出を保持する。
    各問題のDequeは、

        [最初のAC前のWA数,
         次のAC前のWA数,
         ...,
         最後のAC後のWA数]

    を表す。
    */
    let mut deques = vec![VecDeque::from([0_i64]); m];

    for &(problem, is_ac) in &submissions {
        if is_ac {
            deques[problem].push_back(0);
        } else {
            *deques[problem].back_mut().unwrap() += 1;
        }
    }

    let mut ac_count = 0_i64;
    let mut wa_count = 0_i64;

    for deque in &deques {
        if deque.len() >= 2 {
            ac_count += 1;
            wa_count += deque[0];
        }
    }

    let mut interval = Interval::new(
        ac_count,
        wa_count,
        deques,
        submissions,
    );

    let mut answers = vec![(0_i64, 0_i64); q];

    let mut current_left = 0_usize;
    let mut current_right = n - 1;

    for query in queries {
        while query.left < current_left {
            current_left -= 1;
            interval.add_from_left(current_left);
        }

        while current_right < query.right {
            current_right += 1;
            interval.add_from_right(current_right);
        }

        while current_left < query.left {
            interval.delete_from_left(current_left);
            current_left += 1;
        }

        while query.right < current_right {
            interval.delete_from_right(current_right);
            current_right -= 1;
        }

        answers[query.index] = (
            interval.ac_count,
            interval.wa_count,
        );
    }

    let mut output = String::new();

    for (ac, wa) in answers {
        output.push_str(&format!("{ac} {wa}\n"));
    }

    print!("{output}");
}