#711676 (Rust) No.1725 [Cherry 3rd Tune D] 無言の言葉

提出ソース

結果

問題	No.1725 [Cherry 3rd Tune D] 無言の言葉
ユーザー	BenkyouFpga
提出日時	2021-10-29 22:55:12
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	819 ms / 4,000 ms
コード長	11,433 bytes
コンパイル時間	12,976 ms
コンパイル使用メモリ	388,040 KB
実行使用メモリ	103,380 KB
最終ジャッジ日時	2024-10-07 12:36:01
合計ジャッジ時間	27,630 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,820 KB
testcase_01	AC	1 ms 6,820 KB
testcase_02	AC	3 ms 6,820 KB
testcase_03	AC	7 ms 6,816 KB
testcase_04	AC	2 ms 6,820 KB
testcase_05	AC	2 ms 6,816 KB
testcase_06	AC	24 ms 6,820 KB
testcase_07	AC	8 ms 6,816 KB
testcase_08	AC	16 ms 6,816 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	8 ms 6,816 KB
testcase_11	AC	2 ms 6,820 KB
testcase_12	AC	24 ms 7,376 KB
testcase_13	AC	26 ms 7,424 KB
testcase_14	AC	226 ms 29,520 KB
testcase_15	AC	29 ms 7,896 KB
testcase_16	AC	38 ms 8,368 KB
testcase_17	AC	71 ms 11,876 KB
testcase_18	AC	270 ms 29,256 KB
testcase_19	AC	66 ms 9,832 KB
testcase_20	AC	27 ms 6,820 KB
testcase_21	AC	313 ms 53,952 KB
testcase_22	AC	445 ms 66,028 KB
testcase_23	AC	414 ms 64,600 KB
testcase_24	AC	314 ms 61,048 KB
testcase_25	AC	483 ms 73,536 KB
testcase_26	AC	390 ms 68,808 KB
testcase_27	AC	338 ms 76,416 KB
testcase_28	AC	525 ms 75,392 KB
testcase_29	AC	514 ms 74,192 KB
testcase_30	AC	453 ms 78,780 KB
testcase_31	AC	327 ms 64,588 KB
testcase_32	AC	538 ms 88,632 KB
testcase_33	AC	537 ms 89,788 KB
testcase_34	AC	548 ms 86,784 KB
testcase_35	AC	554 ms 82,892 KB
testcase_36	AC	554 ms 86,332 KB
testcase_37	AC	799 ms 103,340 KB
testcase_38	AC	819 ms 103,316 KB
testcase_39	AC	795 ms 103,380 KB
testcase_40	AC	807 ms 103,336 KB
testcase_41	AC	795 ms 103,360 KB
testcase_42	AC	1 ms 6,816 KB
testcase_43	AC	66 ms 43,776 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: unused import: `std::cmp`
 --> src/main.rs:2:5
  |
2 | use std::cmp;
  |     ^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `std::cmp::min`
 --> src/main.rs:3:5
  |
3 | use std::cmp::min;
  |     ^^^^^^^^^^^^^

warning: unused import: `std::collections::BTreeMap`
 --> src/main.rs:4:5
  |
4 | use std::collections::BTreeMap;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: unused import: `std::process`
 --> src/main.rs:5:5
  |
5 | use std::process;
  |     ^^^^^^^^^^^^

warning: unused import: `std::collections::HashSet`
 --> src/main.rs:8:5
  |
8 | use std::collections::HashSet;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^

warning: unused import: `std::collections::BTreeSet`
  --> src/main.rs:10:5
   |
10 | use std::collections::BTreeSet;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: unused import: `std::collections::BinaryHeap`
  --> src/main.rs:12:5
   |
12 | use std::collections::BinaryHeap;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: unused imports: `Hash`, `Hasher`
  --> src/main.rs:13:17
   |
13 | use std::hash::{Hash, Hasher};
   |                 ^^^^  ^^^^^^

warning: unnecessary parentheses around `while` condition
   --> src/main.rs:143:10
    |
143 |     while(b>0){
    |          ^   ^
    |
    = note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
    |
143 -     while(b>0){
143 +     while b>0 {
    |

warning: unnecessary parentheses around `while` condition
   --> src/main.rs:159:14
    |
159 |         while(n != 0){
    |              ^      ^
    |
help: remove these parentheses
    |
159 -         while(n != 0){
159 +         while n != 0 {
    |

warning: unnecessary parentheses around `if` condition
   --> src/main.rs:160:16
    |
160 |             if (n&1 == 1){ans = ans*x%MODu;}
    |                ^        ^
    |
help: remove these parentheses
    |
160 -             if (n&1 == 1){ans = ans*x%MODu;}
160 +             if n&1 == 1 {ans = ans*x%MODu;}
    |

warning: unnecessary p

ソースコード

raw source code

use std::cmp::Ordering;
use std::cmp;
use std::cmp::min;
use std::collections::BTreeMap;
use std::process;
use std::cmp::Ord;
use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;
use std::collections::BTreeSet;
use std::mem;
use std::collections::BinaryHeap;
use std::hash::{Hash, Hasher};

pub struct Scanner<R> {
    stdin: R,
}
 
impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        std::str::from_utf8(&buf).unwrap()
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


pub trait BinarySearch<T> {
    fn lower_bound(&self, x:&T) -> usize;
    fn upper_bound(&self, x:&T) -> usize;
}

impl<T: Ord> BinarySearch<T> for VecDeque<T>{
    fn lower_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less => {
                    low = mid + 1;
                }
                Ordering::Equal | Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }

    fn upper_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less | Ordering::Equal => {
                    low = mid + 1;
                }
                Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }
}
impl<T: Ord> BinarySearch<T> for [T]{
    fn lower_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less => {
                    low = mid + 1;
                }
                Ordering::Equal | Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }

    fn upper_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less | Ordering::Equal => {
                    low = mid + 1;
                }
                Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }
}
fn comb(a:usize, b:usize,  fac:&Vec<usize>, ifac:&Vec<usize>)->usize{
        let mut a = a;
        let mut b = b;
        if a == 0 && b == 0{return 1;}
        if a<b || a<0{return 0;}
        let mut tmp = ifac[a-b]*ifac[b]%MODu;
        return tmp * fac[a]%MODu;
}
fn nHr(n:usize, r:usize, fac:&Vec<usize>, ifac:&Vec<usize>)->usize{
    if n == 0 && r == 0{
        return 1;
    }
    return comb(n+r-1, r, fac, ifac);
}
fn modinv(a:usize, M:usize)->usize{
    let mut b = M as i64;
    let mut u = 1 as i64;
    let mut v = 0 as i64;
    let mut a = a as i64;
    let mut m = M as i64;
    while(b>0){
        let mut t = a/b;
        a -= t*b;
        mem::swap(&mut a, &mut b);
        u-=t*v;
        mem::swap(&mut u, &mut v);
    }
    u%=m;
    if u<0{u+=m;}
    return u as usize;

}
fn modpow(x:usize, n:usize) -> usize{
        let mut ans = 1;
        let mut n = n as usize;
        let mut x = x;
        while(n != 0){
            if (n&1 == 1){ans = ans*x%MODu;}
            x = x*x%MODu;
            n = n>>1;
        }
        ans
}
fn modpow2(x:i64, n:i64, m:i32) -> i64{
        let mut ans = 1;
        let mut n = n as i64;
        let mut x = x;
        while(n != 0){
            if (n&1 == 1){ans = ans*x%m as i64;}
            x = x*x%m as i64;
            n = n>>1;
        }
        ans
}


fn invs(max:usize)->(Vec<usize>, Vec<usize>){
    let mut fac = vec![0;max+1];
    let mut ifac = vec![0;max+1];
    fac[0] = 1;
    ifac[0] = 1;
    for i in 0..max{

        fac[i+1] = fac[i] * (i+1)%MODu;
        ifac[i+1] = ifac[i] * modpow(i+1, MODu - 2)%MODu;
    }
    (fac, ifac)
}

#[derive(Copy, Clone, Eq, PartialEq)]
struct x{    
             a:i64,   
             b:i64, 
             c:i64,   
             d:i64,   
}            
impl Ord for x{
    fn cmp(&self, other:&Self)->Ordering{
                 (other.b * (self.a)).cmp(&((self.b)*other.a))
             }        
         }            
         impl PartialOrd for x {
             fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
                 Some(self.cmp(other))
             }        
         }          
fn gcd(a:usize, b:usize)->usize{
    if b==0{return a;}
    return gcd(b, a%b);
}
fn prime_factor(n:usize)->HashMap<usize, usize>{
    let mut res = HashMap::new();
    let mut n = n;
    for i in 2..n{
        if i*i>n{break;}
        while(n%i==0){
            *res.entry(i).or_insert(0)+=1;
            n/=i;
        }
    }
    if n != 1{
        res.insert(n, 1);
    }
    res
}
fn usize_multiply_is_overflow(a:usize, b:usize)->bool{
    if a<std::usize::MAX/b{
        return false;
    }
    else{
        return true;
    }
}

fn pow2(x:usize, n:usize) -> usize{
        let mut ans = 1;
        let mut n = n;
        let mut x = x;
        while(n != 0){
            if (n&1 == 1){
                if usize_multiply_is_overflow(ans, x){
                    return 0;
                }
                ans = ans*x;

            }
            n = n>>1;
            if n == 0{
                break;
            }
            if usize_multiply_is_overflow(x, x){
                return 0;
            }
            x = x*x;

        }
        ans
}

fn tmp(x:usize, y:usize)->usize{
    let mut ub = x+1;
    let mut lb = 1;
    while(ub-lb>1){
        let mut mid = (ub+lb)/2;
        let mut now = pow2(mid, y);
        let mut ok = true;
        if now == 0{
            ok = false;
        }
        if now>x {
            ok = false;
        }
        if ok{
            lb = mid;
        }
        else{
            ub = mid;
        }
    }
    return lb;
}

struct segment_tree<I, Op>{
    n: usize,
    dat: Vec<I>,
    op:Op,
    e:I,
}
impl<I, Op> segment_tree<I, Op>


    where Op: Fn(I, I) -> I, I:Copy{

        pub fn new(n_:usize, op: Op, e:I)->Self{
            let mut n = 1;
            while(n<n_){n*=2;}
            segment_tree{n: n, dat:vec![e; 2*n-1], op:op, e:e}
        }
        pub fn update(&mut self, k:usize, a:I){
            let mut k = k;
            k += self.n-1;
            self.dat[k] = a;
            while(k>0){
                k = (k-1)/2;
                self.dat[k] = (self.op)(self.dat[k*2 + 1], self.dat[k*2+2]);
            }
        }

        pub fn query_sub(&self, a:usize, b:usize, k:usize, l:usize, r:usize) -> I{
            if r<=a || b<=l{return self.e;}
            if a<=l && r<=b{return self.dat[k];}
            else{
                let mut vl = self.query_sub(a, b, k*2+1, l, (l+r)/2);
                let mut vr = self.query_sub(a, b, k*2+2, (l+r)/2, r);
                return (self.op)(vl, vr);
            }
        }
        pub fn query(&self, a:usize, b:usize)->I{
            return self.query_sub(a, b, 0, 0, self.n);
        }
    }
fn matmul_m(A:&Vec<Vec<i64>>, B:&Vec<Vec<i64>>) -> Vec<Vec<i64>>{
    let mut C = vec![vec![0;B[0].len()];A.len()];
    for i in 0..A.len(){
        for k in 0..B.len(){
            for j in 0..B[0].len(){
                C[i][j] += A[i][k]*B[k][j];
                C[i][j] %= MOD;
            }
        }
    }
    return C;
}
fn matpow(A:&mut Vec<Vec<i64>>, n:usize) -> Vec<Vec<i64>>{
    let mut B = vec![vec![0;A.len()];A.len()];
    for i in 0..A.len(){
        B[i][i] = 1;
    }
    let mut n = n;
    let mut tmp = A.clone();
    while(n>0){
        if n&1 == 1{B = matmul_m(&B, &tmp);}
        tmp = matmul_m(&tmp, &tmp);
        n>>=1;
    }
    return B;
}

fn solve(){
    let sssss = std::io::stdin();
    let mut sc = Scanner { stdin: sssss.lock() };
    let mut x:String = sc.read();
    let mut x:Vec<char> = x.chars().collect();
    let mut y:String = sc.read();
    let mut y:Vec<char> = y.chars().collect();
    let mut cx = vec![vec![0;x.len()+1];26];
    let mut cy = vec![vec![0;y.len()+1];26];
    for i in 0..x.len(){
        cx[x[i] as usize- 'a' as usize][i+1]+=1;
        for j in 0..26{
            cx[j][i+1]+=cx[j][i];
        }
    }

    for i in 0..y.len(){
        cy[y[i] as usize- 'a' as usize][i+1]+=1;
        for j in 0..26{
            cy[j][i+1]+=cy[j][i];
        }
    }



    let mut Q:usize = sc.read();

    let mut L = x.len();
    let mut size=  vec![];
    size.push(0);
    size.push(L);
    let mut now = 1;

    while(L<usize::pow(10, 18)){
        now+=1;
        L = y.len()+L*2;
        size.push(L);
    }

    fn dfs(l:usize, 
           r:usize, 
           cx:&Vec<Vec<usize>>, 
           cy:&Vec<Vec<usize>>, 
           size:&Vec<usize>, 
           c:usize,
           dp:&mut HashMap<(usize, usize, usize), usize>
           )->usize{
        if dp.contains_key(&(l, r, c)){
            return dp[&(l, r, c)];
        }

        let mut level = size.lower_bound(&r);
        if l>r{
            return 0;
        }
        if level == 1{
            return cx[c][r]-cx[c][l-1];
        }
        if level == 0{
            return 0;
        }
        let mut leng = size[level];
        let mut befl = size[level-1];
        let mut a = befl;
        let mut b = befl+cy[0].len()-1;

        let mut res = 0usize;
        if r<=a{
            res+=dfs(1, r, cx, cy, size, c, dp)
        }
        else if a<r && r<=b{
            res+=dfs(1, a, cx, cy, size, c, dp)+cy[c][r-a];
        }
        else{
            res+=dfs(1, a, cx, cy, size, c, dp)+cy[c][b-a]+dfs(befl+1-(r-b), befl, cx, cy, size, c, dp);
        }
        if l-1<=a{
            res-=dfs(1, l-1, cx, cy, size, c, dp);
        }
        else if a<l-1 && l-1<=b{
            res-=dfs(1, a, cx, cy, size, c, dp)+cy[c][l-1-a];
        }
        else{
            res-=dfs(1, a, cx, cy, size, c, dp)+cy[c][b-a]+dfs(befl+1-(l-1-b), befl, cx, cy, size, c, dp);
        }
        dp.insert((l, r, c), res);
        return res;
    }
    let mut dp = HashMap::new();

    for _ in 0..Q{
        let mut l:usize = sc.read();
        let mut r:usize = sc.read();
        let mut c:char = sc.read();
        let mut cc = c as usize - 'a' as usize;
        println!("{}", dfs(l, r, &cx, &cy, &size, cc, &mut dp));
    }













    










}






fn main(){
    solve();
}



const PI:f64 = std::f64::consts::PI;
pub static MOD:i64    = 1000000007;
pub static MODu:usize = 998244353;
pub static MODi32:i32 = 1000000007;
pub static eps:f64 = 1e-6;
const INF: i64 = 1 << 60;
const INFu:usize = 1<<62;
const INFu128:u128 = 1<<126;

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード