Submission #1038929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038929		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	216 ms	194004 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 1e5+7;
struct tri
{
    struct node
    {
        vector<ll> cnt; ll child[4];
        node() {for (ll i = 0; i < 4; i++) child[i] = 0;}
    };
    vector<node> trie = {node()};
    void add(string& x, ll id)
    {
        ll u = 0;
        for (ll i = 0; i < x.size(); i++)
        {
            if (!trie[u].child[x[i]-'A']) {trie.pb(node()); trie[u].child[x[i]-'A'] = trie.size()-1;}
            trie[u].cnt.pb(id); u = trie[u].child[x[i]-'A'];
        }
        trie[u].cnt.pb(id);
    } 
    ll get(string& x)
    {
        ll u = 0;
        for (ll i = 0; i < (ll)x.size(); i++)
        {
            if (!trie[u].child[x[i]-'A']) return -1;
            u = trie[u].child[x[i]-'A'];
        }
        return u;
    }
    ll qget(string& x, ll l, ll r)
    {
        ll u = 0;
        for (ll i = 0; i < (ll)x.size(); i++)
        {
            if (!trie[u].child[x[i]-'A']) return 0;
            u = trie[u].child[x[i]-'A'];
        }
        return upper_bound(trie[u].cnt.begin(),trie[u].cnt.end(),r)-lower_bound(trie[u].cnt.begin(),trie[u].cnt.end(),l);
    }
} tri1, tri2;
char trans(char x) 
{
    if (x == 'A') return 'A';
    if (x == 'U') return 'B';
    if (x == 'G') return 'C';
    return 'D';
}
ll n, m;
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    cin >> n >> m;
    vector<string> ss(n+1);
    for (ll i = 1; i <= n; i++) cin >> ss[i];
    sort(ss.begin(),ss.end());
    for (ll i = 1; i <= n; i++) 
    {
        string s = ss[i];
        for (char& j : s) j = trans(j); 
        tri1.add(s,i);
        reverse(s.begin(),s.end());
        tri2.add(s,i);
    }
    for (ll i = 1; i <= m; i++)
    {
        string a, b; cin >> a >> b;
        for (char& j : a) j = trans(j);
        for (char& j : b) j = trans(j);
        reverse(b.begin(),b.end());
        ll id = tri1.get(a);
        if (id == -1) {cout << 0 << '\n'; continue;}
        ll l = tri1.trie[id].cnt.front(), r = tri1.trie[id].cnt.back();
        cout << tri2.qget(b,l,r) << '\n';
    }
}

Compilation message (stderr)

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

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