Submission #1158540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158540		ReLice	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	1596 ms	17884 KiB

selling_rna

#include <bits/stdc++.h>
#define ll long long
#define ld double
#define pb push_back
#define pf push_front
#define ins insert
#define fr first
#define sc second
#define endl "\n"
#define ar array
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
void start(){ios_base::sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);}

const ll inf = 1e17;
const ll mod = 1e9 + 7;
const ll N = 2e5 + 8;

void solve() {
    ll i, j;

    ll n, m;
    cin>>n>>m;

    vector<vector<ll>> ans(n);

    ll pp[N];
    pp[0] = 1;
    for(i=1;i<N;i++) pp[i] = pp[i - 1] * 29 % mod;

    for(i=0;i<n;i++){
        string s;
        cin>>s;

        ans[i].resize(s.size(), 0);

        for(j=0;j<(ll)s.size();j++){
            ans[i][j] = (j ? ans[i][j - 1] : 0) * 29 + s[j] - 'A' + 1;
            ans[i][j] %= mod;
        }
    }

    for(i=0;i<m;i++){
        string p, q;
        cin>>p>>q;

        ll x = 0, y = 0;
        ll a = p.size(), b = q.size();

        for(j=0;j<a;j++){
            x = x * 29 + (p[j] - 'A' + 1);
            x %= mod;
        }

        for(j=0;j<b;j++){
            y = y * 29 + (q[j] - 'A' + 1);
            y %= mod;
        }

        ll sum = 0;

        for(j=0;j<n;j++){
            ll c = ans[j].size();
            if(c >= max(a, b)){
                if(ans[j][a - 1] == x && (ans[j][c - 1] - (c - b ? ans[j][c - b - 1] * pp[b] % mod : 0) + mod) % mod == y){
                    sum++;
                }
            }
        }

        cout<<sum<<endl;
    }
}

signed main(){
    start();

    ll t = 1;
    //cin>>t;

    while(t--) solve();
}

/*

*/

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40