Submission #1248152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248152		ezgamee	Selling RNA Strands (JOI16_selling_rna)	C++20	0 / 100	1599 ms	144616 KiB

selling_rna

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define fi first
#define se second
#define fr front
#define pfr push_front
#define pofr pop_front
#define pob pop_back
#define For(a,b,c,d) for(auto a = b;(d > 0&&a <= c) || (d < 0&&a >= c);a+=d)
#define MSK(k) (1ULL<<(k))
#define PROBLEM ""

using namespace std;

const int maxN = 1e5,maxNode = 2e6;;
int n,m;
string str[maxN+7];
struct nodeTrie{
    int child[3];
    vector<int> index;

    nodeTrie(){
        memset(child,0,sizeof child);
        index.clear();
    }
}trie[maxNode+7];
int cntNode;

int findId(char c){
    if(c == 'A')
        return 0;
    if(c == 'G')
        return 1;
    return 2;
}

void addTrie(string s,int index){
    int u = 0;
    for(auto c : s){
        int id = findId(c);
        if(!trie[u].child[id])
            trie[u].child[id] = ++cntNode;
        u = trie[u].child[id];
        trie[u].index.pb(index);
    }
    return;
}

int cnp(string s){
    int l = 1,r = n;
    while(l <= r){
        int mid = (l+r)>>1;
        str[mid] >= s ? r = mid-1 : l = mid+1;
    }
    return l;
}

vector<int> getIndex(string s){
    int u = 0;
    for(auto c : s){
        int id = findId(c);
        if(!trie[u].child[id])
            return trie[0].index;
        u = trie[u].child[id];
    }
    return trie[u].index;
}

int main()
{
//    freopen(PROBLEM".INP","r",stdin);
//    freopen(PROBLEM".OUT","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    For(i,1,n,1)
        cin>>str[i];
    sort(str+1,str+n+1);
    For(i,1,n,1){
        reverse(str[i].begin(),str[i].end());
        addTrie(str[i],i);
        reverse(str[i].begin(),str[i].end());
    }
    For(i,1,m,1){
        string p,q;cin>>p>>q;
        int l = cnp(p);
        p += 'Z';
        int r = cnp(p);
        reverse(q.begin(),q.end());
        vector<int> index = getIndex(q);
        sort(index.begin(),index.end());
        int idLow = lower_bound(index.begin(),index.end(),l)-index.begin();
        int idUp = lower_bound(index.begin(),index.end(),r)-index.begin();
        cout<<idUp-idLow<<"\n";
//        cout<<" "<<l<<" "<<r<<"\n";
    }
    return 0;
}

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