Submission #1081597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081597		danglayloi1	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	216 ms	148096 KiB

selling_rna

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
const int nx=1e5+5;
const int N=2e6+5;
int getid(char c)
{
    if(c=='A')
        return 0;
    if(c=='C')
        return 1;
    if(c=='G')
        return 2;
    return 3;
}
int n, m;
string a[nx];
struct trie
{
    struct dak
    {
        int child[4], l, r;
        dak()
        {
            memset(child, -1, sizeof(child));
            l=inf, r=0;
        }
    };
    vector<dak> nod;
    trie()
    {
        nod.emplace_back();
    }
    void add(string s, int id)
    {
        int pos=0;
        for(int i = 0; i < s.size(); i++)
        {
            int c=getid(s[i]);
            if(nod[pos].child[c]==-1)
                nod[pos].child[c]=nod.size(), nod.emplace_back();
            pos=nod[pos].child[c];
            nod[pos].l=min(nod[pos].l, id);
            nod[pos].r=max(nod[pos].r, id);
        }
    }
    ii get_range(string s)
    {
        int pos=0;
        for(int i = 0; i < s.size(); i++)
        {
            int c=getid(s[i]);
            if(nod[pos].child[c]==-1)
                return ii(-1, -1);
            pos=nod[pos].child[c];
        }
        return ii(nod[pos].l, nod[pos].r);
    }
} T;
struct rev_trie
{
    struct dak
    {
        int child[4];
        vector<int> ids;
        dak()
        {
            memset(child, -1, sizeof(child));
            ids.clear();
        }
    };
    vector<dak> nod;
    rev_trie()
    {
        nod.emplace_back();
    }
    void add(string s, int id)
    {
        int pos=0;
        for(int i = s.size()-1; i >= 0; i--)
        {
            int c=getid(s[i]);
            if(nod[pos].child[c]==-1)
                nod[pos].child[c]=nod.size(), nod.emplace_back();
            pos=nod[pos].child[c];
            nod[pos].ids.emplace_back(id);
        }
    }
    int query(string s, ii f)
    {
        int pos=0;
        for(int i = s.size()-1; i >= 0; i--)
        {
            int c=getid(s[i]);
            if(nod[pos].child[c]==-1)
                return 0;
            pos=nod[pos].child[c];
        }
        int l=lower_bound(nod[pos].ids.begin(), nod[pos].ids.end(), f.fi)-nod[pos].ids.begin();
        int r=upper_bound(nod[pos].ids.begin(), nod[pos].ids.end(), f.se)-nod[pos].ids.begin();
        return r-l;
    }
} T1;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        cin>>a[i];
    sort(a+1, a+n+1);
    for(int i = 1; i <= n; i++)
    {
        T.add(a[i], i);
        T1.add(a[i], i);
    }
    while(m--)
    {
        string x, y;
        cin>>x>>y;
        ii cur=T.get_range(x);
        cout<<T1.query(y, cur)<<'\n';
    }
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void trie::add(std::string, int)':
selling_rna.cpp:41:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int i = 0; i < s.size(); i++)
      |                        ~~^~~~~~~~~~
selling_rna.cpp: In member function 'std::pair<int, int> trie::get_range(std::string)':
selling_rna.cpp:54:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int i = 0; i < s.size(); i++)
      |                        ~~^~~~~~~~~~

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