結果

問題 No.1725 [Cherry 3rd Tune D] 無言の言葉
コンテスト
ユーザー 沙耶花
提出日時 2021-10-29 22:09:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 323 ms / 4,000 ms
コード長 1,845 bytes
コンパイル時間 5,048 ms
コンパイル使用メモリ 253,884 KB
最終ジャッジ日時 2025-01-25 08:57:14
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:99:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   99 |                 scanf("%lld %lld",&L,&R);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

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