結果

問題 No.1725 [Cherry 3rd Tune D] 無言の言葉
ユーザー 沙耶花沙耶花
提出日時 2021-10-29 22:09:26
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 157 ms / 4,000 ms
コード長 1,845 bytes
コンパイル時間 4,735 ms
コンパイル使用メモリ 257,380 KB
実行使用メモリ 44,416 KB
最終ジャッジ日時 2024-04-16 15:00:01
合計ジャッジ時間 9,057 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 4 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 12 ms
5,376 KB
testcase_07 AC 6 ms
5,376 KB
testcase_08 AC 9 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 6 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 13 ms
5,760 KB
testcase_13 AC 13 ms
5,888 KB
testcase_14 AC 83 ms
6,016 KB
testcase_15 AC 15 ms
6,272 KB
testcase_16 AC 19 ms
6,784 KB
testcase_17 AC 33 ms
6,912 KB
testcase_18 AC 102 ms
5,632 KB
testcase_19 AC 27 ms
5,376 KB
testcase_20 AC 12 ms
5,376 KB
testcase_21 AC 89 ms
5,376 KB
testcase_22 AC 102 ms
16,384 KB
testcase_23 AC 105 ms
15,104 KB
testcase_24 AC 69 ms
11,648 KB
testcase_25 AC 125 ms
24,064 KB
testcase_26 AC 98 ms
19,200 KB
testcase_27 AC 96 ms
26,880 KB
testcase_28 AC 137 ms
25,600 KB
testcase_29 AC 130 ms
24,576 KB
testcase_30 AC 121 ms
29,056 KB
testcase_31 AC 76 ms
15,104 KB
testcase_32 AC 155 ms
38,784 KB
testcase_33 AC 157 ms
39,808 KB
testcase_34 AC 150 ms
36,864 KB
testcase_35 AC 148 ms
33,152 KB
testcase_36 AC 154 ms
36,352 KB
testcase_37 AC 115 ms
5,376 KB
testcase_38 AC 113 ms
5,376 KB
testcase_39 AC 111 ms
5,376 KB
testcase_40 AC 112 ms
5,376 KB
testcase_41 AC 110 ms
5,376 KB
testcase_42 AC 2 ms
5,376 KB
testcase_43 AC 46 ms
44,416 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf (long long)1000000000000000000
long long len[30];

vector<vector<long long>> Xcnt(26),Ycnt(26);
vector<vector<long long>> Fcnt(26);
long long m,nn;
long long get(int f, long long n,int ind,bool flag){	
//cout<<f<<','<<n<<','<<flag<<endl;
	if(n==0)return 0;
	if(f==0){
		if(flag){
			return Xcnt[ind][n];
		}
		else{
			//cout<<Xcnt[ind].back()<<','<<Xcnt[ind][Xcnt.size()-1-n]<<endl;
			//cout<<Xcnt[ind].back() - Xcnt[ind][nn-n]<<endl;
			return Xcnt[ind].back() - Xcnt[ind][nn-n];
		}
	}

	long long ret = 0LL;
	if(len[f-1]>=n){
		return get(f-1,n,ind,true);
	}

	ret += Fcnt[ind][f-1];
	n -= len[f-1];

	if(n<=m){
		//cout<<flag<<endl;
		if(flag){
			ret += Ycnt[ind][n];
		}
		else{
			ret += Ycnt[ind].back() - Ycnt[ind][m-n];
		}
		return ret;
	}

	ret += Ycnt[ind].back();
	n -= m;
	return ret + get(f-1,n,ind,false);
	
}

int main(){
	
	string X,Y;
	cin>>X>>Y;
	
	nn = X.size();
	m = Y.size();
	
	len[0] = nn;
	for(int i=1;i<30;i++){
		len[i] = min(len[i-1] * 2 + m, Inf);
	}

	rep(i,26){
		Xcnt[i].resize(nn+1,0);
		rep(j,nn){
			if(i==X[j]-'a'){
				Xcnt[i][j+1] = 1;
			}
			Xcnt[i][j+1] += Xcnt[i][j];
		}
	}
	//rep(i,Xcnt[0].size())cout<<Xcnt[0][i]<<endl;
	rep(i,26){
		Ycnt[i].resize(m+1,0);
		rep(j,m){
			if(i==Y[j]-'a'){
				Ycnt[i][j+1] = 1;
			}
			Ycnt[i][j+1] += Ycnt[i][j];
		}
	}
	
	rep(i,26){
		Fcnt[i].resize(30,0LL);
		Fcnt[i][0] = Xcnt[i].back();
		
		for(int j=1;j<30;j++){
			Fcnt[i][j] = min(Inf,Fcnt[i][j-1]*2 + Ycnt[i].back());
		}	
	}
	
	int Q;
	cin>>Q;
	rep(_,Q){
		long long L,R;
		scanf("%lld %lld",&L,&R);
		char c;
		cin>>c;
		cout<<get(29,R,c-'a',true) - get(29,L-1,c-'a',true)<<endl;
	}
	
	return 0;
	
}
0