Submission #858976

#	Time	Username	Problem	Language	Result	Execution time	Memory
858976		hungt58	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	227 ms	444240 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define ll int
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
typedef pair<ll,ll> ii;
const ll maxn=5e6+10;
ll n,m,tim[3];
string s[100010];
struct di
{
    ll child[27],in,ou;
};
vector<ll> c[maxn];
di a[maxn],b[maxn];
void update(ll w)
{
    string sa=s[w];;
    ll u=0;
    for (ll i=0;i<sa.size();i++)
    {
    if (a[u].child[sa[i]-'A'+1]==0)
    {

        a[u].child[sa[i]-'A'+1]=++tim[1];
        a[tim[1]].in=w;
    }
    u=a[u].child[sa[i]-'A'+1];
    a[u].ou=w;

    }
    u=0;
    for (ll i=sa.size()-1;i>=0;i--)
    {
    if (b[u].child[sa[i]-'A'+1]==0)
    {
        b[u].child[sa[i]-'A'+1]=++tim[2];
    }
    u=b[u].child[sa[i]-'A'+1];

    c[u].push_back(w);

    }
}
void get (string sa,string sb)
{
    ll u=0,ua=0;
    for (ll i=0;i<sa.size();i++)
    if (a[u].child[sa[i]-'A'+1]!=0) u=a[u].child[sa[i]-'A'+1]; else {cout<<"0";return;}

    for (ll i=sb.size()-1;i>=0;i--)
    if (b[ua].child[sb[i]-'A'+1]!=0) ua=b[ua].child[sb[i]-'A'+1]; else {cout<<"0";return;}
    c[ua].push_back(1000000);
    ll w=lower_bound(c[ua].begin(),c[ua].end(),a[u].in)-c[ua].begin();
    ll wa=upper_bound(c[ua].begin(),c[ua].end(),a[u].ou)-c[ua].begin();
    wa--;

    if (w>wa) {cout<<"0";return;}
    cout<<wa-w+1;
}
int main()
{
    
    ios_base :: sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for (ll i=1;i<=n;i++)
    cin>>s[i];
    sort (s+1,s+n+1);
    for (ll i=1;i<=n;i++) update(i);
    for (ll i=1;i<=m;i++)
    {
        cin>>s[1]>>s[2];
        get (s[1],s[2]);
        cout<<'\n';
    }


}

Compilation message (stderr)

selling_rna.cpp: In function 'void update(int)':
selling_rna.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (ll i=0;i<sa.size();i++)
      |                 ~^~~~~~~~~~
selling_rna.cpp: In function 'void get(std::string, std::string)':
selling_rna.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (ll i=0;i<sa.size();i++)
      |                 ~^~~~~~~~~~

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