Submission #1282790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282790		Faisal_Saqib	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	1627 ms	855352 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e6+10,mod=1e9+7,base=26;
string s[N],p[N],q[N];
ll pw[N],inv[N];
char cur[]={'A','A','C','G','U'};
vector<ll> pre[N];
ll gethash(int i,int l,int r) // 1-base and inc inc
{
    ll k1=(pre[i][r]-pre[i][l-1]+mod)%mod;
    // pre[r] has power (r-1) we need its power to be r-l
    // pre[l] has power l-1 we need its power to be l-1
    // so mul by inverse of 
    return (k1*inv[l-1])%mod;
}
int powmod(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)
            ans=(1ll*ans*a)%mod;
        a=(1ll*a*a)%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
 ios::sync_with_stdio(0);
 cout.tie(0);
 cin.tie(0);
 pw[0]=1;
 for(int i=1;i<N;i++)
 {
    pw[i]=(1ll*pw[i-1]*base)%mod;
 }
 inv[N-1]=powmod(pw[N-1],mod-2);
 for(int i=N-2;i>=0;i--)
 {
    inv[i]=(1ll*inv[i+1]*base)%mod;
 }
 int n,m;
 cin>>n>>m;
 for(int i=0;i<n;i++)
 {
    cin>>s[i];
    int sz=s[i].size();
    pre[i].resize(sz+1);
    for(int j=0;j<sz;j++)
    {
        for(int p=1;p<=4;p++)
        {
            if(s[i][j]==cur[p])
            {
                pre[i][j+1]=(1ll*pre[i][j]+1ll*p*pw[j])%mod;
            }
        }
    }
}
vector<int> pos,qos;
for(int i=0;i<m;i++)
{
    cin>>p[i]>>q[i];
    pos.push_back(p[i].size());
    qos.push_back(q[i].size());
}
sort(begin(pos),end(pos));
pos.resize(unique(begin(pos),end(pos))-begin(pos));
sort(begin(qos),end(qos));
qos.resize(unique(begin(qos),end(qos))-begin(qos));
map<ll,int> cnt;
// ll st=4e18;
// cout<<st<<endl;
for(int i=0;i<n;i++)
{
    // check prefix only for length in pos, and suffix for length in q
    int sz=s[i].size();
    for(auto&l:pos)
    {
        if(l>sz)break;
        int h1=gethash(i,1,l);
        // till here iteration can be maximum sum(len(s[i]))<=2e6
        for(auto&l1:qos) // sqrt(2e6)
        {
            if(l1>sz)break;
            int h2=gethash(i,sz-l1+1,sz);
            // cout<<"For "<<i<<' '<<l<<' '<<l1<<' '<<h1<<' '<<h2<<endl;
            cnt[(1ll*h1*mod)+h2]++;
        }
    }
}
for(int i=0;i<m;i++)
{
    int hash=0;
    for(int j=0;j<p[i].size();j++)
    {
        for(int k=1;k<=4;k++)
        {
            if(p[i][j]==cur[k])
            {
                hash=(1ll*hash+1ll*k*pw[j])%mod;
            }
        }
    }
    int hash1=0;
    for(int j=0;j<q[i].size();j++)
    {
        for(int k=1;k<=4;k++)
        {
            if(q[i][j]==cur[k])
            {
                hash1=(1ll*hash1+1ll*k*pw[j])%mod;
            }
        }
    }
    // cout<<hash<<' '<<hash1<<endl;
    cout<<cnt[(1ll*hash*mod)+hash1]<<'\n';
}
 // A C G U 
 // 0 1 2 3
}

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