oj.uz

Submission #857216

# Submission time Handle Problem Language Result Execution time Memory
857216 2023-10-05T15:26:02 Z Canhhao Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 116 ms 156904 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int T = 1e6 + 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27228 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 6 ms 27228 KB Output is correct
4 Correct 6 ms 27252 KB Output is correct
5 Correct 7 ms 27224 KB Output is correct
6 Correct 6 ms 27228 KB Output is correct
7 Correct 6 ms 27228 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 116 ms 156904 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 28752 KB Output is correct
2 Correct 19 ms 28508 KB Output is correct
3 Correct 23 ms 28496 KB Output is correct
4 Correct 18 ms 28252 KB Output is correct
5 Correct 20 ms 28288 KB Output is correct
6 Correct 23 ms 28508 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27228 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 6 ms 27228 KB Output is correct
4 Correct 6 ms 27252 KB Output is correct
5 Correct 7 ms 27224 KB Output is correct
6 Correct 6 ms 27228 KB Output is correct
7 Correct 6 ms 27228 KB Output is correct
8 Runtime error 116 ms 156904 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -