Submission #74290850

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s1,s2;
vector<ll>sz;
vector<vector<ll>>p1,p2;
map<pair<ll,char>,ll>dp;

ll get_cnt(ll id,ll l,ll r,char ch){
    ll c=ch-'a';
    if(id==1)return p1[c][r]-p1[c][l-1];
    else return p2[c][r]-p2[c][l-1];
}

ll dfs(ll idx,ll l,ll r,char ch){
    if(l>r)return 0;

    if(l==1 && r==sz[idx]){
        if(dp.count({idx,ch}))return dp[{idx,ch}];
    }

    if(idx==1)return get_cnt(1,l,r,ch);
    if(idx==2)return get_cnt(2,l,r,ch);

    ll left_size=sz[idx-1];
    ll res;

    if(r<=left_size)res=dfs(idx-1,l,r,ch);
    else if(l>left_size)res=dfs(idx-2,l-left_size,r-left_size,ch);
    else{
        ll part1=dfs(idx-1,l,left_size,ch);
        ll part2=dfs(idx-2,1,r-left_size,ch);
        res=part1+part2;
    }

    if(l==1 && r==sz[idx])dp[{idx,ch}]=res;

    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>s1>>s2;
    ll q;
    cin>>q;

    p1.assign(26,vector<ll>(s1.size()+1,0));
    p2.assign(26,vector<ll>(s2.size()+1,0));

    for(ll i=0;i<s1.size();i++){
        for(ll c=0;c<26;c++)p1[c][i+1]=p1[c][i];
        p1[s1[i]-'a'][i+1]++;
    }

    for(ll i=0;i<s2.size();i++){
        for(ll c=0;c<26;c++)p2[c][i+1]=p2[c][i];
        p2[s2[i]-'a'][i+1]++;
    }

    sz.push_back(0);
    sz.push_back(s1.size());
    sz.push_back(s2.size());

    while(sz.back()<(ll)1e18){
        ll nxt=sz[sz.size()-1]+sz[sz.size()-2];
        sz.push_back(min(nxt,(ll)1e18));
    }

    ll last=sz.size()-1;

    while(q--){
        ll l,r;
        char ch;
        cin>>l>>r>>ch;
        cout<<dfs(last,l,r,ch)<<endl;
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'int main()':
./Main.cpp:52:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(ll i=0;i<s1.size();i++){
      |                ~^~~~~~~~~~
./Main.cpp:57:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(ll i=0;i<s2.size();i++){
      |                ~^~~~~~~~~~

Judge Result