Submission #297791

#	Time	Username	Problem	Language	Result	Execution time	Memory
297791		XmtosX	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	494 ms	541304 KiB

selling_rna

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
const int N=1e5+5;
int n,m,ans,l,r;
string s[N],S;
pair<pair<string,string>,int> p[N];
struct trie
{
    vector<int> v;
    trie *a[26]={0};
    void insert(int pos,int idx)
    {
        v.push_back(idx);
        if (pos<0)
            return;
        int x= S[pos]-'A';
        if (!a[x])
            a[x]=new trie();
        a[x]->insert(pos-1,idx);
    }
    int query (int pos)
    {
        if (pos==S.size())
        {
            if (v.empty()||v.back()!=n)
                v.push_back(n);
            int i= lower_bound(v.begin(),v.end(),l)-v.begin();
            int j= lower_bound(v.begin(),v.end(),r)-v.begin();
            return j-i;
        }
        int x= (S[pos]-'A');
        if (!a[x])
            return 0;
        return a[x]->query(pos+1);
    }
}tree;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >>n>>m;
    for (int i=0;i<n;i++)
        cin >>s[i];
    for (int i=0;i<m;i++)
        cin >>p[i].first.first>>p[i].first.second,p[i].second=i;
    sort(s,s+n);
    for (int i=0;i<n;i++)
    {
        S=s[i];
        tree.insert(S.size()-1,i);
    }
    int idx1=0,idx2=1;
    for (int i=0;i<m;i++)
    {
        string s1=p[i].first.first;
        string s2=p[i].first.second;
        int low,high,mid;
        low=0,high=n-1;
        l=r=n;
        while (low<=high)
        {
            mid=(low+high)/2;
            if (s[mid].substr(0,min(s[mid].size(),s1.size()))>=s1)
            {
                l=mid;
                high=mid-1;
            }
            else
                low=mid+1;
        }
        low=0,high=n-1;
        while (low<=high)
        {
            mid=(low+high)/2;
            if (s[mid].substr(0,min(s[mid].size(),s1.size()))>s1)
                high=mid-1;
            else
            {
                r=mid;
                low=mid+1;
            }
        }
        r++;
        reverse(s2.begin(),s2.end());
        S=s2;
        cout <<tree.query(0)<<"\n";
    }
    return 0;
}
/*
2 3
AUGC
AGC
G C
AU C
A C

3 3
AA
AA
AGA
AA AA
AG GA
AG GA

8 7
GCGCUACCCCAACACAAGGCAAGAUAUA
G
GGAC
GCGG
U
GCGCUACCCCAACACAAGGCAAGAUGGUC
GCCG
GCGCUGA
GCGCUACCC A
GCGCUACCCC AC
GCG C
GCGC A
G G
G C
G GGA
*/

Compilation message (stderr)

selling_rna.cpp: In member function 'int trie::query(int)':
selling_rna.cpp:24:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         if (pos==S.size())
      |             ~~~^~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:54:9: warning: unused variable 'idx1' [-Wunused-variable]
   54 |     int idx1=0,idx2=1;
      |         ^~~~
selling_rna.cpp:54:16: warning: unused variable 'idx2' [-Wunused-variable]
   54 |     int idx1=0,idx2=1;
      |                ^~~~

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