Submission #74290437

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
#define INF 1e18
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl "\n"
#define vi vector<int>
#define vs vector<string>
#define pii pair<int, int>
#define mii map<int, int>
#define seti set<int>
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define pr(a) cout<<a<<endl;
#define printList(a) for (auto &x : a) cout << x << " ";cout<<endl;
#define printMap(a) for (auto &x : a) cout << x.ff << " " << x.ss << endl;
#define PI 3.1415926535897932384626
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define ps(x,y) fixed<<setprecision(y)<<x
#define w(x) int x; cin>>x; while(x--)
#define sortall(x) sort(all(x))
#define vvi vector<vector<int>>
#define vvvi vector<vector<vector<int>>>
#define vpii vector<pii>
#define matrix(N,M) vvi matrix(N, vi(M, 0));
#define printMatrix(matrix) for(auto &x:matrix){for(auto &y:x)cout<<y<<" ";cout<<endl;}
#define inputMatrix(matrix) for(auto &x:matrix)for(auto &y:x)cin>>y;
#define sortMatrix(matrix) for(auto &x:matrix)sortall(x);
#define rotateMatrix(matrix) reverse(all(matrix));for(int i=0;i<matrix.size();i++)for(int j=0;j<i;j++)swap(matrix[i][j],matrix[j][i]);
#define matrixSum(matrix) int sum=0;for(auto &x:matrix)for(auto &y:x)sum+=y;cout<<sum<<endl;
#define matrixProduct(matrix) int product=1;for(auto &x:matrix)for(auto &y:x)product*=y;cout<<product<<endl;
#define matrixMax(matrix) int mx=INT_MIN;for(auto &x:matrix)for(auto &y:x)mx=max(mx,y);cout<<mx<<endl;
#define matrixMin(matrix) int mn=INT_MAX;for(auto &x:matrix)for(auto &y:x)mn=min(mn,y);cout<<mn<<endl;
#define matrixTranspose(matrix) for(int i=0;i<matrix.size();i++)for(int j=0;j<i;j++)swap(matrix[i][j],matrix[j][i]);
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define maxEle(a) *max_element(all(a))
#define minEle(a) *min_element(all(a))
#define sumEle(a) accumulate(all(a),0)
#define productEle(a) accumulate(all(a),1,multiplies<int>())
#define maxIndex(a) max_element(all(a))-a.begin()
#define minIndex(a) min_element(all(a))-a.begin()
#define findIndex(a,x) find(all(a),x)-a.begin()
#define findEle(a,x) find(all(a),x)!=a.end()
#define countEle(a,x) count(all(a),x)
#define lowerEle(a,x) lower_bound(all(a),x)-a.begin()
#define upperEle(a,x) upper_bound(all(a),x)-a.begin()
#define gcd(a,b) __gcd(a,b)
#define hi cout<<"Hello\n";
#define yes cout<<"Yes\n";
#define no cout<<"No\n";

int Binary_exp(int a, int b, int c ){
    int ans = 1;
    while(b){
        if(b&1){
            ans =(ans*1LL*a) % c;
        }
        a = (a*1LL*a) % c;
        b/=2;
    }
    return ans;
}

int C(int n, int r) { if (r > n - r) r = n - r; int ans = 1; for (int i = 1; i <= r; i++) { ans *= n - r + i; ans /= i; } return ans; }
int modInv(int a) { return Binary_exp(a, MOD - 2, MOD); }
bool isPrime(int n){ if(n<=1)return false; for(int i=2;i*i<=n;i++)if(n%i==0)return false; return true; }

template<class T>ostream &operator<<(ostream &os,const vector<T> &p){for(auto &it:p)os<<it<<' ';return os;}
template<class T>void dbs(string str,T t){cerr<<str<<":"<<t<<endl;}
template<class T,class...S>void dbs(string str,T t,S... s){int idx=str.find(',');cerr<<str.substr(0,idx)<<":"<<t<<",";dbs(str.substr(idx+1),s...);}

const int MAX_N = 92;

int solve(int ind, int tar, vector<vector<int>> &ans, vector<int> &a, string x, string y) {
    if (ind <= 0) return 0;
    int tot = 0;
    int maxi = MAX_N;
            
    while (maxi > 2) {
        if (ind >= a[maxi]) {
            tot += ans[maxi][tar];
            return tot;
        }
                
        if (ind <= a[maxi - 1]) {
            maxi = maxi - 1;
        } else {
            tot += ans[maxi - 1][tar];
            ind -= a[maxi - 1];
            maxi = maxi - 2;
        }
    }

    if (maxi == 1) {
        for (int i = 0; i < min((int)x.size(), ind); i++) {
            if (x[i] - 'a' == tar) tot++;
        }
    } else if (maxi == 2) {
        for (int i = 0; i < min((int)y.size(), ind); i++) {
            if (y[i] - 'a' == tar) tot++;
        }
    }
    return tot;
}

void solved(){
    string x, y;
    cin >> x >> y;

    int q;
    cin >> q;
    vector<int> a(MAX_N + 1);
    vector<vector<int>> ans(MAX_N + 1, vector<int>(26, 0));
    int maxi = INT_MAX;

    a[1] = x.size();
    a[2] = y.size();
    for (char c : x) ans[1][c - 'a']++;
    for (char c : y) ans[2][c - 'a']++;

    for (int i = 3; i <= MAX_N; i++) {
        a[i] = min((int)2e18, a[i - 1] + a[i - 2]);
        for (int j = 0; j < 26; j++) {
            ans[i][j] = ans[i - 1][j] + ans[i - 2][j];
        }
    }

    while (q--) {
        int l, r;
        char C;
        cin >> l >> r >> C;
        int tar = C - 'a';


        cout << solve(r, tar, ans, a,x,y) - solve(l - 1, tar, ans, a,x,y) << "\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin>>t;
    while(t--){
        solved();
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'void solved()':
./Main.cpp:123:9: warning: unused variable 'maxi' [-Wunused-variable]
  123 |     int maxi = INT_MAX;
      |         ^~~~

Judge Result