Submission #1070537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070537		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	1394 ms	490208 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

long long a[2000005][5], b[2000005][5], l[2000005][5], r[2000005][5], id1=1, id2=1;
vector<long long> ans[2000005][5];
string s[100005], pre, suf;

string fix(string t)
{
    long long n=t.size(), i;
    string t1="";
    for (i=0; i<n; i++)
    {
        if (t[i]=='C') {t1+='a';}
        else if (t[i]=='U') {t1+='b';}
        else if (t[i]=='G') {t1+='c';}
        else {t1+='d';};
    };
    return t1;
}

void add(string t, long long k)
{
    long long n=t.size(), i, j=0;
    for (i=0; i<n; i++)
    {
        if (a[j][t[i]-'a']==0) {a[j][t[i]-'a']=id1++; l[j][t[i]-'a']=r[j][t[i]-'a']=k;}
        else {r[j][t[i]-'a']=k;};
        j=a[j][t[i]-'a'];
    };
}

void addsuf(string t, long long k)
{
    long long n=t.size(), i, j=0;
    for (i=0; i<n; i++)
    {
        if (b[j][t[i]-'a']==0) {b[j][t[i]-'a']=id2++;};
        ans[j][t[i]-'a'].push_back(k);
        j=b[j][t[i]-'a'];
    };
}

pair<long long, long long> solvepre(string t)
{
    long long n=t.size(), i, j=0;
    for (i=0; i<n-1; i++)
    {
        if (a[j][t[i]-'a']==0) {return {0LL, 0LL};};
        j=a[j][t[i]-'a'];
    };
    return {l[j][t[n-1]-'a'], r[j][t[n-1]-'a']};
}

vector<long long> solvesuf(string t)
{
    long long n=t.size(), i, j=0;
    vector<long long> v;
    for (i=0; i<n-1; i++)
    {
        if (b[j][t[i]-'a']==0) {return v;};
        j=b[j][t[i]-'a'];
    };
    return ans[j][t[n-1]-'a'];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, m, i;
    pair<long long, long long> p;
    vector<long long> v;
    cin >> n >> m;
    for (i=1; i<=n; i++)
    {
        cin >> s[i];
        s[i]=fix(s[i]);
    };
    sort(s+1, s+n+1);
    for (i=1; i<=n; i++)
    {
        add(s[i], i);
        reverse(s[i].begin(), s[i].end());
        addsuf(s[i], i);
    };
    while (m--)
    {
        cin >> pre >> suf;
        pre=fix(pre); suf=fix(suf);
        p=solvepre(pre);
        reverse(suf.begin(), suf.end());
        v=solvesuf(suf);
        cout << upper_bound(v.begin(), v.end(), p.second)-lower_bound(v.begin(), v.end(), p.first) << "\n";
    };
}

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