I am getting time limit exceeded for 3 test cases. I used rolling hash for solving this. Any suggestions fot optimizing it?

Thank You.

https://cses.fi/problemset/task/2102/

My Solution

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1000000007;
class RollHash{
public:
    int Hash[1000005];
    RollHash(){
        memset(Hash,0,sizeof Hash);
    }
    void fillRoll(string s)
    {
        int n = s.length();
        int x = 131;
        for(int i=0;i<n;i++)
        {
            Hash[i+1] = (Hash[i] + x*(s[i]-'a'+1))%mod;
            x*=131;
            x%=mod;
        }
    }
    int power(int a,int b)
    {
        if(b == 0)return 1;
     
        int ans = 1;
        while(b > 0)
        {
           
            if(b%2)
                ans = (ans*a)%mod;
            a = (a*a)%mod;
     
            b/=2;
     
        }
        return ans;
    }
    int get(int l,int r)
    {
        return ((Hash[r] - Hash[l-1] + mod)*power(power(131,l-1),mod-2))%mod;
    }
};
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    string word;
    cin >> word;
    int n = word.length();
 
    RollHash r;
 
    r.fillRoll(word);
    int m;
    cin >> m;
    while(m--)
    {
        int flag = 0;
        string s;
        cin >> s;
        int hash = 0;
        int x = 131;
 
        for(int i=0;i<s.length();i++)
        {
            hash = (hash + x*(s[i]-'a'+1))%mod;
            x*=131;
            x%=mod;
        }
 
        for(int i=1;i+s.length()-1<=n;i++)
        {
            int x = i;
            int y = i + s.length() - 1;
            if(r.get(x,y) == hash)
            {
                flag = 1;
                break;
            }
        }
        if(flag)cout << "YES\n";
        else
            cout << "NO\n";
    }
 
    return 0;
}

First time I am trying to set problems for a local coding event. I will happy to hear regarding suggestion for generating test cases in bulk. like in terms of 10^5 numbers.

Thanks.

You are given an array A of size N; find the minimum value of K such that number of subarrays with XOR value at most K is at least X:

• 1 <=N << 10^5
• 1 <= X <= N*(N+2)/2

• 1 <= A[i] <= 10^6

  For Input :
  4 7
  1 2 3 4    
  Output : 4
  

I had using sublime text for contests. But when I use syntax like vector,map it autosuggest like std::vector like older C++ versions. I want to use it with C++ versions like C++14 or C++17 for simplicity.

How to do that ? Also I want to have quick syntax suggestions with this How to do that ?

Waiting for help ....

Thank You.

Problem Statement`` ================= : Given a list which initially contains 0, the following queries can be performed:

0 X : Add X to the List

1 X : Replace each element in List With its XOR with X (i.e. Replace A with A^X where is ^ is an XOR operation)

Return a list in increasing order after all queries.

-------- Sample :

-------- Q=5

0 4

0 2

1 4

0 5

1 8

Answer : 8 12 13 14

Let me know the concept in this problem :

Thanks.

Update : Got The Solution : Thanks

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
signed main()
{
    vector<int>v;
    int effect=0;
    int q;
    cin >> q;
    v.push_back(0);
    while(q--)
    {
        int type,x;
        cin >> type >> x;
        if(type==0)
        {
            v.push_back(x);
            v.back()^=effect;
        }
        else
        {
            effect^=x;
        }
    }
    for(int i=0;i<v.size();i++)
    {
        v[i]^=effect;
    }
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++)
        cout<<v[i]<<' ';

}

Thanks CodeForces Community ... This Was my First Attempt to CF Blogs..