Submission #1313389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313389		something	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	388 ms	554880 KiB

selling_rna

#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define lb long double
#define flip(i) ((i)%2)^1
#define el "\n"
#define fre(name) freopen(name".INP","r",stdin); freopen(name".OUT","w",stdout)
using namespace std;
const int N=2e5+5;
const int M=4e6+5;
string s[N];
int n,m;
int curtrieid;
string a,b;

struct NODE
{
    int child[26];
    int mx=0,mn=0;
    NODE()
    {
        for(int i=0;i<26;i++)
            child[i]=-1;
    }
}node[M];

vector<int>reverse_end[M];

void add(string &x,int id)
{
    int p=0;
    for(auto z : x)
    {
        if(node[p].child[z-'A']==-1) node[p].child[z-'A']=++curtrieid;
        //cout<<p<<" "<<node[p].child[z-'A']<<" "<<z<<el;
        p=node[p].child[z-'A'];
         node[p].mx=id;
         if(!node[p].mn) node[p].mn=id;
    }
}

void reverseadd(string &x,int id)
{
    int p=0;
    for(int i=x.size()-1;i>=0;i--)
    {
        if(node[p].child[x[i]-'A']==-1) node[p].child[x[i]-'A']=++curtrieid;
         //cout<<p<<" "<<node[p].child[x[i]-'A']<<" "<<x[i]<<el;
        p=node[p].child[x[i]-'A'];
        reverse_end[p].push_back(id);
    }
}

int findd(string &x)
{
   int p=0;
   for(auto z : x)
   {
      if(node[p].child[z-'A']==-1) return 0;
      p=node[p].child[z-'A'];
   }
   return p;
}



void solve()
{
     int begin_node=findd(a);
     reverse(b.begin(),b.end());
     int end_node=findd(b);

     if(!begin_node||!end_node)
     {
        cout<<0<<el;
        return;
     }

     /*cout<<begin_node<<" "<<end_node<<el;
     cout<<node[begin_node].mn<<" "<<node[begin_node].mx<<el;*/
      
     int l=lower_bound(reverse_end[end_node].begin(), reverse_end[end_node].end(),node[begin_node].mn)-reverse_end[end_node].begin()+1;
     int r=upper_bound(reverse_end[end_node].begin(), reverse_end[end_node].end(),node[begin_node].mx)-reverse_end[end_node].begin()+1;

     cout<<max(0,r-l)<<el;
}

signed main()
{
    ios_base::sync_with_stdio (false);
    cin.tie(0); cout.tie(0);
   // fre("NTHANH");
    
    cin>>n>>m;

    for(int i=1;i<=n;i++)
        cin>>s[i];

    sort(s+1,s+1+n);

    for(int i=1;i<=n;i++)
    {
      add(s[i],i);
      reverseadd(s[i],i);
    }

    while(m--)
    {
        cin>>a>>b;
        solve();
    }
    return 0;
}

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