Submission #1279934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279934		nvthinh	Selling RNA Strands (JOI16_selling_rna)	C++20	0 / 100	99 ms	42648 KiB

selling_rna

/* https://oj.uz/problem/view/JOI16_selling_rna */

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define bit(n,i) ((n>>i)&1)
#define Fup(i,x,y) for(i=x;i<=y;i++)
#define Fdo(i,x,y) for(i=x;i>=y;i--)
#define LOG 20
#define maxN 100005
using namespace std;
int n,m,i,cnt_01=0,cnt_02=0,res;
string s[maxN],t[maxN],p,q;
struct DATA_01{ int id,l,r; }trie_01[200005][26];
int trie_02[200005][26];
vector<int>X[200005];
void add_01(string& s,int ID){
int i,u,k;
    u=0;
    for(i=0;i<s.size();i++){
        k=s[i]-'A';
        if(trie_01[u][k].id==0){
            ++cnt_01;
            trie_01[u][k]={cnt_01,ID,ID};
        }
        else{
            trie_01[u][k].l=min(trie_01[u][k].l,ID);
            trie_01[u][k].r=max(trie_01[u][k].r,ID);
        }
        u=trie_01[u][k].id;
    }
return;
}
pair<int,int>get_01(string& s){
int i,u,k;
pair<int,int>res={1e9,-1e9};
    u=0;
    for(i=0;i<s.size();i++){
        k=s[i]-'A';
        if(trie_01[u][k].id==0)return {0,0};
        res.fi=min(res.fi, trie_01[u][k].l );
        res.se=max(res.se, trie_01[u][k].r );
        u=trie_01[u][k].id;
    }
return res;
}
void add_02(string& s,int ID){
int u,i,k;
    u=0;
    for(i=0;i<s.size();i++){
        k=s[i]-'A';
        if(trie_02[u][k]==0){ trie_02[u][k]=++cnt_02; }
        u=trie_02[u][k];
        X[u].push_back(ID);
    }
}
vector<int> get_02(string& s){
int u,i,k;
    u=0;
    for(i=0;i<s.size();i++){
        k=s[i]-'A';
        if(trie_02[u][k]==0){ vector<int>I; I.clear(); return I; }
        u=trie_02[u][k];
    }
    return X[u];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(i=1;i<=n;i++) cin>>s[i];
    sort(s+1,s+n+1);
    for(i=1;i<=n;i++){
        t[i]=s[i];
        reverse(t[i].begin(),t[i].end());
    }
    for(i=1;i<=n;i++){
        add_01(s[i],i);
        add_02(t[i],i);
    }
    while(m--){
        cin>>p>>q;
        reverse(q.begin(),q.end());
        auto T_01=get_01(p);
        auto T_02=get_02(q);
        res=upper_bound(T_02.begin(), T_02.end(), T_01.se)
          - lower_bound(T_02.begin(), T_02.end(), T_01.fi);
        cout<<res<<'\n';
    }
return 0;
}
/*
3 3
AA
AA
AGA
AA AA
AG GA
AG GA
*/

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