Submission #624348

#	Time	Username	Problem	Language	Result	Execution time	Memory
624348		duypd4206	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	830 ms	154392 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define pb push_back
#define all(x) (x.begin(), x.end())
typedef pair<int,int> ii;

const int maxn = 1e5 + 1;
const int oo = 1e9 + 7;
const int mod = 1e9 + 7;

struct node
{
    int nxt[4] ;
    node()
    {
        memset(nxt, -1, sizeof(nxt));
    }
    vector<int> id;
};
int aa(char c)
{
    if(c == 'A') return 0;
    if(c == 'C') return 1;
    if(c == 'G') return 2;
    if(c == 'U') return 3;
}
node tmp;
struct Trie
{
    vector<node> trie;
    Trie() {trie.emplace_back(tmp);}
    void add(string s, int id)
    {
        int i = 0;
        for(auto c : s)
        {
            int ii = aa(c);
            if(trie[i].nxt[ii] == -1)
            {
                trie[i].nxt[ii] = trie.size();
                trie.emplace_back(tmp);
            }
            trie[i].id.pb(id);
            i = trie[i].nxt[ii];
        }
        trie[i].id.pb(id);
    }

    int get(string s)
    {
        int i = 0;
        for(auto c :s)
        {
            int ii = aa(c);
            if(trie[i].nxt[ii] == -1)
                return -1;
            i = trie[i].nxt[ii];
        }
        return i;
    }

};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//#ifndef ONLINE_JUDGE
//#define file ""
//    freopen(file"inp","r",stdin);
//    freopen(file"out","w",stdout);
//#endif //ONLINE_JUDGE
    int n, m;
    cin >> n >> m;
    Trie trie, rtrie;
    string s;
    for(int i = 1; i <= n; i++)
    {
        cin >> s;
        trie.add(s, i);
        reverse(s.begin(), s.end());
        rtrie.add(s, i);
    }
    string p, q;
    for(int i = 1; i <= m; i++)
    {
        cin >> p >> q;
        reverse(q.begin(), q.end());
        int sp = trie.get(p), sq = rtrie.get(q);
        if(sp == -1 || sq == -1)
        {
            cout << 0 << "\n";
            continue;
        }
        vector<int> vp = trie.trie[sp].id;
        vector<int> vq = rtrie.trie[sq].id;
        int l = vp.front(), r = vp.back();
        int ll = lower_bound(vq.begin(), vq.end(), l) - vq.begin();
        int rr = upper_bound(vq.begin(), vq.end(), r) - vq.begin();
        if(ll == vq.size() || ll > r)
            cout << 0 << "\n";
        else cout << rr - ll << "\n";
    }
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:102:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         if(ll == vq.size() || ll > r)
      |            ~~~^~~~~~~~~~~~
selling_rna.cpp: In function 'int aa(char)':
selling_rna.cpp:29:1: warning: control reaches end of non-void function [-Wreturn-type]
   29 | }
      | ^

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