Submission #1279940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279940		manh	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	200 ms	236752 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define exe cerr<<1.0*clock()/CLOCKS_PER_SEC;
#define io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define iof(file) freopen(file ".inp","r",stdin);freopen(file ".out","w",stdout);
#define ll long long
#define eb emplace_back
#define T tuple<int,int,int>
#define P pair<int,int>

const ll N=1e5+5,lim=1e7,mod=1e9+7;

int n,m;
string a[N];

int f(char x){
    if (x=='A') return 0;
    else if (x=='U') return 1;
    else if (x=='G') return 2;
    return 3;
}

struct trie{
    struct node{
        node* child[4];
        vector<int> ans;
        int l,r;

        node(){
            l=0;
            r=0;
            memset(child,0,sizeof child);
        }
    };

    node* root = new node();

    void upd1(string s,int idx){
        node* id=root;
        for (char i:s){
            int k=f(i);
            if (!id->child[k]){
                id->child[k] = new node();
                id=id->child[k];
                id->l=idx;
                id->r=idx;
            }
            else{
                id=id->child[k];
                id->r=idx;
            }
        }
    }

    void upd2(string s,int idx){
        node* id=root;
        for (char i:s){
            int k=f(i);
            if (!id->child[k]) id->child[k] = new node();
            id=id->child[k];
            id->ans.eb(idx);
        }
    }

    P get1(string s){
        node* id=root;
        for (char i:s){
            int k=f(i);
            if (!id->child[k]) return {0,0};
            id=id->child[k];
        }
        return {id->l,id->r};
    }

    int get2(string s,P lim){
        node* id=root;
        for (char i:s){
            int k=f(i);
            if (!id->child[k]) return 0;
            id=id->child[k];
        }

        return upper_bound(id->ans.begin(),id->ans.end(),lim.second)-
               lower_bound(id->ans.begin(),id->ans.end(),lim.first);
    }

} trie1,trie2;

int main(){
    io
   // iof("io")
    cin>>n>>m;
    for (int i=1;i<=n;++i) cin>>a[i];
    sort(a+1,a+n+1);

    for (int i=1;i<=n;++i){
        trie1.upd1(a[i],i);
        reverse(a[i].begin(),a[i].end());
        trie2.upd2(a[i],i);
    }

    for (int i=1;i<=m;++i){
        string p,q; cin>>p>>q;
        reverse(q.begin(),q.end());
        P lim=trie1.get1(p);
        cout<<trie2.get2(q,lim)<<'\n';
    }
    exe
    return 0;
}

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