Submission #857218

#	Time	Username	Problem	Language	Result	Execution time	Memory
857218		Canhhao	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	158 ms	217396 KiB

selling_rna

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

const int N = 1e5 + 5;
const int T = 5e6 + 5;

int trie1[T][4], trie2[T][4], L[T], R[T], ctr[300];
string str[N];
vector<int> list_index[T];

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    ctr['A'] = 0; ctr['C'] = 1; ctr['G'] = 2; ctr['U'] = 3;

    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) 
        cin >> str[i];
    
    sort (str + 1, str + n + 1);

    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= n; i++) {
        int u = 0;
        for (int j = 0; j < str[i].size(); j++) {
            if (trie1[u][ctr[str[i][j]]] == 0)
                trie1[u][ctr[str[i][j]]] = ++ cnt1;
            u = trie1[u][ctr[str[i][j]]];
            if (L[u] == 0) L[u] = i;
            L[u] = min(L[u], i);
            R[u] = max(R[u], i);
        }

        u = 0;
        for (int j = str[i].size() - 1; j >= 0; j--) {
            if (trie2[u][ctr[str[i][j]]] == 0)
                trie2[u][ctr[str[i][j]]] = ++ cnt2;
            u = trie2[u][ctr[str[i][j]]];
            list_index[u].push_back(i);
        }
    }

    for (int i = 1; i <= cnt2; i++)
        sort(list_index[i].begin(), list_index[i].end());

    while (m --) {
        string P, Q; cin >> P >> Q;
        int u = 0;
        for (int j = 0; j < P.size(); j++) {
            if (trie1[u][ctr[P[j]]] == 0) {
                u = -1;
                break;
            } 
            u = trie1[u][ctr[P[j]]];
        }

        if (u == -1) {
            cout << "0\n";
            continue;
        }

        int v = 0;
        for (int j = Q.size() - 1; j >= 0; j--) {
            if (trie2[v][ctr[Q[j]]] == 0) {
                v = -1;
                break;
            }
            v = trie2[v][ctr[Q[j]]];
        }
        
        if (v == -1) {
            cout << "0\n";
            continue;
        }

        int x = lower_bound(list_index[v].begin(), list_index[v].end(), L[u]) - list_index[v].begin();
        int y = upper_bound(list_index[v].begin(), list_index[v].end(), R[u]) - list_index[v].begin();

        cout << max(0, y - x) << "\n";
    }
}

Compilation message (stderr)

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for (int j = 0; j < str[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~
selling_rna.cpp:27:39: warning: array subscript has type 'char' [-Wchar-subscripts]
   27 |             if (trie1[u][ctr[str[i][j]]] == 0)
      |                                       ^
selling_rna.cpp:28:39: warning: array subscript has type 'char' [-Wchar-subscripts]
   28 |                 trie1[u][ctr[str[i][j]]] = ++ cnt1;
      |                                       ^
selling_rna.cpp:29:39: warning: array subscript has type 'char' [-Wchar-subscripts]
   29 |             u = trie1[u][ctr[str[i][j]]];
      |                                       ^
selling_rna.cpp:37:39: warning: array subscript has type 'char' [-Wchar-subscripts]
   37 |             if (trie2[u][ctr[str[i][j]]] == 0)
      |                                       ^
selling_rna.cpp:38:39: warning: array subscript has type 'char' [-Wchar-subscripts]
   38 |                 trie2[u][ctr[str[i][j]]] = ++ cnt2;
      |                                       ^
selling_rna.cpp:39:39: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |             u = trie2[u][ctr[str[i][j]]];
      |                                       ^
selling_rna.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for (int j = 0; j < P.size(); j++) {
      |                         ~~^~~~~~~~~~
selling_rna.cpp:51:34: warning: array subscript has type 'char' [-Wchar-subscripts]
   51 |             if (trie1[u][ctr[P[j]]] == 0) {
      |                                  ^
selling_rna.cpp:55:34: warning: array subscript has type 'char' [-Wchar-subscripts]
   55 |             u = trie1[u][ctr[P[j]]];
      |                                  ^
selling_rna.cpp:65:34: warning: array subscript has type 'char' [-Wchar-subscripts]
   65 |             if (trie2[v][ctr[Q[j]]] == 0) {
      |                                  ^
selling_rna.cpp:69:34: warning: array subscript has type 'char' [-Wchar-subscripts]
   69 |             v = trie2[v][ctr[Q[j]]];
      |                                  ^

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