제출 #1170815

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170815		AlgorithmWarrior	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	263 ms	142072 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

int const MAX=2e6+5;
int Tpref[MAX][4];
int Tsuf[MAX][4];
int l[MAX],r[MAX];
vector<int>ind[MAX];
int n,m;
vector<string>v;
int trans[300];
int total_p,total_s;

void minself(int& x,int val){
    if(x>val)
        x=val;
}

void maxself(int& x,int val){
    if(x<val)
        x=val;
}

void add(int T[][4],string& sir,int id,int nod,int type,int orig_id,int& total_id){
    if(type==1){
        minself(l[nod],orig_id);
        maxself(r[nod],orig_id);
    }
    else
        ind[nod].push_back(orig_id);
    if(id<(int)sir.size()){
        int& nou=T[nod][trans[sir[id]]];
        if(nou==0){
            nou=++total_id;
            if(type==1){
                l[nou]=n+1;
                r[nou]=0;
            }
        }
        add(T,sir,id+1,nou,type,orig_id,total_id);
    }
}

void read(){
    cin>>n>>m;
    int i;
    for(i=1;i<=n;++i){
        string s;
        cin>>s;
        v.push_back(s);
    }
    l[0]=n+1;
    r[0]=0;
    sort(v.begin(),v.end());
    trans['A']=0;
    trans['C']=1;
    trans['G']=2;
    trans['U']=3;
    for(i=0;i<n;++i){
        add(Tpref,v[i],0,0,1,i+1,total_p);
        reverse(v[i].begin(),v[i].end());
        add(Tsuf,v[i],0,0,2,i+1,total_s);
    }
}

int get_node(int T[][4],string& sir,int id,int nod){
    if(id==(int)sir.size())
        return nod;
    int& nou=T[nod][trans[sir[id]]];
    if(nou)
        return get_node(T,sir,id+1,nou);
    return 0;
}

void process_queries(){
    int i;
    for(i=1;i<=m;++i){
        string pref,suf;
        cin>>pref>>suf;
        int nodP=get_node(Tpref,pref,0,0);
        reverse(suf.begin(),suf.end());
        int nodS=get_node(Tsuf,suf,0,0);
        if(nodP && nodS)
            cout<<upper_bound(ind[nodS].begin(),ind[nodS].end(),r[nodP])-lower_bound(ind[nodS].begin(),ind[nodS].end(),l[nodP])<<'\n';
        else
            cout<<0<<'\n';
    }
}

int main()
{
    read();
    process_queries();
    return 0;
}

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