Submission #219405

#	Time	Username	Problem	Language	Result	Execution time	Memory
219405		MKopchev	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	440 ms	322880 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e5+42;

int n,q;

struct info
{
    int nxt[26];
};

vector< info > trie;

int pointer=0;

vector< vector<int> > seen;

int create_info()
{
    seen.push_back({});

    info idle;
    for(int i=0;i<26;i++)
        idle.nxt[i]=-1;

    trie.push_back(idle);
    pointer++;

    //cout<<"create_info= "<<pointer-1<<endl;

    return pointer-1;
}

pair<string,int> inp[nmax];

void add(int id)
{

    int current=0;
    for(int i=0;i<inp[id].first.size();i++)
    {
        char c=inp[id].first[i];

        if(trie[current].nxt[c-'A']==-1)
        {
            int mem=create_info();
            trie[current].nxt[c-'A']=mem;
        }

        //cout<<trie[current].nxt[c-'A']<<endl;

        current=trie[current].nxt[c-'A'];

        seen[current].push_back(id);
    }
}
string sorted_strings[nmax];

string en;

int query(int l,int r)
{
    int current=0;
    for(int i=0;i<en.size();i++)
    {
        char c=en[i];

        if(trie[current].nxt[c-'A']==-1)return 0;
        else current=trie[current].nxt[c-'A'];
    }

    int u=lower_bound(seen[current].begin(),seen[current].end(),l)-seen[current].begin();
    int v=upper_bound(seen[current].begin(),seen[current].end(),r)-seen[current].begin();
    return v-u;
}
int ask()
{
    string st;
    cin>>st>>en;

    reverse(en.begin(),en.end());

    int l=lower_bound(sorted_strings+1,sorted_strings+n+1,st)-sorted_strings;
    st[st.size()-1]++;
    int r=lower_bound(sorted_strings+1,sorted_strings+n+1,st)-sorted_strings;r--;

    //cout<<"query "<<l<<" "<<r<<endl;

    if(l>r)return 0;
    return query(l,r);
}

int main()
{
    create_info();

    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();

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

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

    for(int i=1;i<=n;i++)
        inp[i]={sorted_strings[i],i};

    for(int i=1;i<=n;i++)
        reverse(inp[i].first.begin(),inp[i].first.end());

    for(int i=1;i<=n;i++)
        add(i);

    for(int i=1;i<=q;i++)
        printf("%i\n",ask());
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void add(int)':
selling_rna.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<inp[id].first.size();i++)
                 ~^~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int query(int, int)':
selling_rna.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<en.size();i++)
                 ~^~~~~~~~~~

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