Submission #1263997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263997		haha	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	196 ms	251684 KiB

selling_rna

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=2e6+5;
const int base=31;
const ll MOD=1e9+7;

int n,m,cur=0,cur1=0;
vector<string> S;
// ACGU
char a[]={'A','C','G','U'};

struct Node
{
    int child[4];
    int l,r;
    vector<int> id;
};
Node nodes[maxn],nodes1[maxn];

int new_node()
{
    cur++;
    memset(nodes[cur].child,-1,sizeof(nodes[cur].child));
    return cur;
}

int new_node1()
{
    cur1++;
    memset(nodes1[cur1].child,-1,sizeof(nodes1[cur1].child));
    return cur1;
}

void add_string(string s,int idx)
{
    int pos=0;
    for(int i=0;i<s.size();i++){
        int c=0;
        for(int x=0;x<4;x++){
            if(s[i]==a[x]) c=x;
        }
        if(nodes[pos].child[c]==-1){
            nodes[pos].child[c]=new_node();
        }
        pos=nodes[pos].child[c];
        if(nodes[pos].l==0) nodes[pos].l=idx;
        nodes[pos].r=idx;
    }
}

void add_string1(string s,int idx)
{
    int pos=0;
    for(int i=0;i<s.size();i++){
        int c=0;
        for(int x=0;x<4;x++){
            if(s[i]==a[x]) c=x;
        }
        if(nodes1[pos].child[c]==-1){
            nodes1[pos].child[c]=new_node1();
        }
        pos=nodes1[pos].child[c];
        nodes1[pos].id.push_back(idx);
    }
}

int main()
{
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    memset(nodes[0].child,-1,sizeof(nodes[0].child));
    memset(nodes1[0].child,-1,sizeof(nodes1[0].child));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        string x;
        cin>>x;
        S.push_back(x);
    }
    sort(S.begin(),S.end());
    for(int i=0;i<S.size();i++){
        add_string(S[i],i+1);
        reverse(S[i].begin(),S[i].end());
        add_string1(S[i],i+1);
    }
    while(m--){
        string p,q;
        cin>>p>>q;
        int pos=0,ans=0;
        bool check=true;
        for(int i=0;i<p.size();i++){
            int c=0;
            for(int x=0;x<4;x++){
                if(p[i]==a[x]) c=x;
            }
            if(nodes[pos].child[c]==-1){
                check=false;
                break;
            }
            pos=nodes[pos].child[c];
        }
        if(check){
            int L=nodes[pos].l;
            int R=nodes[pos].r;
            pos=0;
            reverse(q.begin(),q.end());
            for(int i=0;i<q.size();i++){
                int c=0;
                for(int x=0;x<4;x++){
                    if(q[i]==a[x]) c=x;
                }
                if(nodes1[pos].child[c]==-1) check=false;
                pos=nodes1[pos].child[c];
            }
            if(!check) cout<<0<<'\n';
            else{
                int ans=0;
                int l=lower_bound(nodes1[pos].id.begin(),nodes1[pos].id.end(),L)-nodes1[pos].id.begin();
                int r=upper_bound(nodes1[pos].id.begin(),nodes1[pos].id.end(),R)-nodes1[pos].id.begin()-1;
                cout<<max(0,r-l+1)<<'\n';
            }
        }
        else cout<<0<<'\n';
    }
}

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