結果

問題 No.2395 区間二次変換一点取得
コンテスト
ユーザー srtry
提出日時 2026-06-27 10:34:14
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 29 ms / 2,000 ms
コード長 2,488 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,252 ms
コンパイル使用メモリ 193,184 KB
実行使用メモリ 9,460 KB
最終ジャッジ日時 2026-06-27 10:34:26
合計ジャッジ時間 4,526 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/* 
 *     Author:  srtry
 *     Created: 2026-06-26T23:33:33+09:00
 *     Coding:  utf-8-unix
 */

use proconio::input;
use std::io::{stdout,Write,BufWriter};


const MAX_N:usize = 100001;

#[inline(always)]
fn add_bit_imos(bit_imos:&mut [isize;MAX_N], size:usize, idx:usize, x:isize) {
    let mut i = idx;
    while i <= size {
        bit_imos[i] += x;
        i += i & (!i + 1);
    }
}

#[inline(always)]
fn sum_bit_imos(bit_imos:&[isize;MAX_N], idx:usize) -> usize {
    let mut i = idx;
    let mut s = 0;
    while i > 0 {
        s += bit_imos[i];
        i -= i & (!i + 1);
    }
    s as usize
}

#[inline(always)]
fn push_usize_to_string(s: &mut String, mut num: usize) {
    if num == 0 {
        // push_zero_to_string(s);
        s.push('0');
        return;
    }

    // String の皮をひんむいて、中身の Vec<u8> を直接操作する（超高速）
    // ※ 整数を文字（ASCII）にするだけなので安全です
    let buf = unsafe { s.as_mut_vec() };
    let start_idx = buf.len();

    // 💡 これがやりたかった「純粋な計算式」！
    // 10で割った余りに '0' のバイト値（48）を足すと、その数字の文字コードになります
    while num > 0 {
        buf.push(b'0' + (num % 10) as u8);
        num /= 10;
    }

    // 逆順に入っているので、この数値の分だけ反転する
    buf[start_idx..].reverse();
}

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

    let out = stdout();
    let mut out = BufWriter::with_capacity(8*2100000,out.lock());
    let mut ans:String = String::with_capacity(8*2100000);

    let mut bit_imos:[isize;MAX_N] = [0;MAX_N];

    // xにi回加算された時のy,z
    let mut mem:[(usize,usize);MAX_N] = [(1,1);MAX_N];
    for i in 1..=q {
        mem[i].1 = (3*mem[i-1].1) % b;  // z_k
        mem[i].0 = (3*mem[i-1].0 % b) + (2*(i+1)*mem[i-1].1 % b); // y_k
        mem[i].0 %= b;
    }

    for (l,m,r) in queries {
        add_bit_imos(&mut bit_imos, n, l, 1);
        add_bit_imos(&mut bit_imos, n, r+1, -1);

        let k:usize= sum_bit_imos(&bit_imos,  m);
        let x:usize = (1 + k) % b;

        push_usize_to_string(&mut ans, x);
        ans.push(' ');
        push_usize_to_string(&mut ans, mem[k].0);
        ans.push(' ');
        push_usize_to_string(&mut ans, mem[k].1);
        ans.push('\n');
    } 
    out.write_all(ans.as_bytes()).unwrap();
    out.flush().unwrap();

}
0