Submission #820012

#	Time	Username	Problem	Language	Result	Execution time	Memory
820012		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	211 ms	275244 KiB

selling_rna

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

int c[256];

class trie_t {
       public:
        int l, r, is_sorted;
        vector<int> index;
        trie_t* g[4];
        trie_t() {
                l = 1e9, r = -1, is_sorted = 0;
                for (int i = 0; i < 4; i++) g[i] = nullptr;
        }

        static void add(trie_t* root, const string& s, int id) {
                for (auto&& x : s) {
                        if (!root->g[c[x]]) {
                                root->g[c[x]] = new trie_t();
                        }
                        root = root->g[c[x]];
                        root->index.emplace_back(id);
                        root->l = min(root->l, id);
                        root->r = max(root->r, id);
                }
        }

        static pair<int, int> get(trie_t* root, const string& s) {
                for (auto&& x : s) {
                        if (!root->g[c[x]]) {
                                return {-1, -1};
                        }
                        root = root->g[c[x]];
                }
                return {root->l, root->r};
        }

        static int solve(trie_t* root, int l, int r, const string& s) {
                for (auto&& x : s) {
                        if (!root->g[c[x]]) {
                                return 0;
                        }
                        root = root->g[c[x]];
                }
                if (!root->is_sorted) sort(root->index.begin(), root->index.end()), root->is_sorted = 1;
                return upper_bound(root->index.begin(), root->index.end(), r) - lower_bound(root->index.begin(), root->index.end(), l);
        }
};

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        c['A'] = 0, c['G'] = 1, c['C'] = 2, c['U'] = 3;
        int n, m;
        cin >> n >> m;
        vector<string> a(n), b(m);
        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a.begin(), a.end());
        trie_t* tree = new trie_t();
        trie_t* rev_tree = new trie_t();
        for (int i = 0; i < n; i++) trie_t::add(tree, a[i], i);
        for (int i = 0; i < n; i++) reverse(a[i].begin(), a[i].end());
        for (int i = 0; i < n; i++) trie_t::add(rev_tree, a[i], i);
        for (int i = 0; i < m; i++) {
                string p, q;
                cin >> p >> q;
                reverse(q.begin(), q.end());
                auto [l, r] = trie_t::get(tree, p);
                cout << (l <= r ? trie_t::solve(rev_tree, l, r, q) : 0) << '\n';
        }
}

Compilation message (stderr)

selling_rna.cpp: In static member function 'static void trie_t::add(trie_t*, const string&, int)':
selling_rna.cpp:18:40: warning: array subscript has type 'char' [-Wchar-subscripts]
   18 |                         if (!root->g[c[x]]) {
      |                                        ^
selling_rna.cpp:19:43: warning: array subscript has type 'char' [-Wchar-subscripts]
   19 |                                 root->g[c[x]] = new trie_t();
      |                                           ^
selling_rna.cpp:21:42: warning: array subscript has type 'char' [-Wchar-subscripts]
   21 |                         root = root->g[c[x]];
      |                                          ^
selling_rna.cpp: In static member function 'static std::pair<int, int> trie_t::get(trie_t*, const string&)':
selling_rna.cpp:30:40: warning: array subscript has type 'char' [-Wchar-subscripts]
   30 |                         if (!root->g[c[x]]) {
      |                                        ^
selling_rna.cpp:33:42: warning: array subscript has type 'char' [-Wchar-subscripts]
   33 |                         root = root->g[c[x]];
      |                                          ^
selling_rna.cpp: In static member function 'static int trie_t::solve(trie_t*, int, int, const string&)':
selling_rna.cpp:40:40: warning: array subscript has type 'char' [-Wchar-subscripts]
   40 |                         if (!root->g[c[x]]) {
      |                                        ^
selling_rna.cpp:43:42: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |                         root = root->g[c[x]];
      |                                          ^

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