oj.uz

Submission #118723

# Submission time Handle Problem Language Result Execution time Memory
118723 2019-06-19T14:13:28 Z IOrtroiii Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 924 ms 700280 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100100;

int to(char c) {
   if (c == 'A') return 0;
   else if (c == 'C') return 1;
   else if (c == 'G') return 2;
   else return 3;
}

int n, q;
string s[N];
int tot;
int l[300 * N];
int r[300 * N];
int sz[300 * N];
int nxt[300 * N][4];
int root;
int T[N << 2];

int nxtNode() {
   return ++tot;
}

void add(int root, string s, int id = 0) {
   int cur = root;
   for (char c : s) {
      c = (int) to(c);
      if (!nxt[cur][c]) {
         nxt[cur][c] = nxtNode();
      }
      cur = nxt[cur][c];
      if (l[cur] == 0) {
         l[cur] = id;
      }
      r[cur] = id;
      ++sz[cur];
   }
}

int getNode(int root, string s) {
   int cur = root;
   for (char c : s) {
      c = (int) to(c);
      if (!nxt[cur][c]) {
         return 0;
      }
      cur = nxt[cur][c];
   }
   return cur;
}

#define mid ((l + r) >> 1)

void build(int v, int l, int r) {
   T[v] = nxtNode();
   for (int i = l; i <= r; ++i) {
      add(T[v], s[i]);
   }
   if (l < r) {
      build(v << 1, l, mid);
      build(v << 1 | 1, mid + 1, r);
   }
}

int getCount(int v, int l, int r, int L, int R, string &s) {
   if (L <= l && r <= R) {
      return sz[getNode(T[v], s)];
   }
   int ans = 0;
   if (L <= mid) ans += getCount(v << 1, l, mid, L, R, s);
   if (mid < R) ans += getCount(v << 1 | 1, mid + 1, r, L, R, s);
   return ans;
}

int solve(string p, string q) {
   int cur = getNode(root, p);
   if (!cur) return 0;
   reverse(q.begin(), q.end());
   return getCount(1, 1, n, l[cur], r[cur], q);
}

int main() {
   ios_base::sync_with_stdio(false);
   cin >> n >> q;
   for (int i = 1; i <= n; ++i) {
      cin >> s[i];
   }
   sort(s + 1, s + 1 + n);
   root = nxtNode();
   for (int i = 1; i <= n; ++i) {
      add(root, s[i], i);
      reverse(s[i].begin(), s[i].end());
   }
   build(1, 1, n);
   while (q--) {
      string u, v;
      cin >> u >> v;
      cout << solve(u, v) << '\n';
   }
}

Compilation message

selling_rna.cpp: In function 'void add(int, std::__cxx11::string, int)':
selling_rna.cpp:32:22: warning: array subscript has type 'char' [-Wchar-subscripts]
       if (!nxt[cur][c]) {
                      ^
selling_rna.cpp:33:20: warning: array subscript has type 'char' [-Wchar-subscripts]
          nxt[cur][c] = nxtNode();
                    ^
selling_rna.cpp:35:23: warning: array subscript has type 'char' [-Wchar-subscripts]
       cur = nxt[cur][c];
                       ^
selling_rna.cpp: In function 'int getNode(int, std::__cxx11::string)':
selling_rna.cpp:48:22: warning: array subscript has type 'char' [-Wchar-subscripts]
       if (!nxt[cur][c]) {
                      ^
selling_rna.cpp:51:23: warning: array subscript has type 'char' [-Wchar-subscripts]
       cur = nxt[cur][c];
                       ^

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 784 ms 657028 KB Output is correct
2 Correct 822 ms 700280 KB Output is correct
3 Correct 432 ms 235004 KB Output is correct
4 Correct 434 ms 229856 KB Output is correct
5 Correct 679 ms 491464 KB Output is correct
6 Correct 667 ms 498700 KB Output is correct
7 Correct 209 ms 93052 KB Output is correct
8 Correct 630 ms 483832 KB Output is correct
9 Correct 564 ms 426900 KB Output is correct
10 Correct 448 ms 316408 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 12488 KB Output is correct
2 Correct 93 ms 13176 KB Output is correct
3 Correct 111 ms 13176 KB Output is correct
4 Correct 92 ms 11596 KB Output is correct
5 Correct 89 ms 12024 KB Output is correct
6 Correct 114 ms 12628 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3584 KB Output is correct
2 Correct 4 ms 3584 KB Output is correct
3 Correct 4 ms 3584 KB Output is correct
4 Correct 5 ms 3584 KB Output is correct
5 Correct 4 ms 3584 KB Output is correct
6 Correct 5 ms 3584 KB Output is correct
7 Correct 5 ms 3712 KB Output is correct
8 Correct 784 ms 657028 KB Output is correct
9 Correct 822 ms 700280 KB Output is correct
10 Correct 432 ms 235004 KB Output is correct
11 Correct 434 ms 229856 KB Output is correct
12 Correct 679 ms 491464 KB Output is correct
13 Correct 667 ms 498700 KB Output is correct
14 Correct 209 ms 93052 KB Output is correct
15 Correct 630 ms 483832 KB Output is correct
16 Correct 564 ms 426900 KB Output is correct
17 Correct 448 ms 316408 KB Output is correct
18 Correct 126 ms 12488 KB Output is correct
19 Correct 93 ms 13176 KB Output is correct
20 Correct 111 ms 13176 KB Output is correct
21 Correct 92 ms 11596 KB Output is correct
22 Correct 89 ms 12024 KB Output is correct
23 Correct 114 ms 12628 KB Output is correct
24 Correct 908 ms 667280 KB Output is correct
25 Correct 924 ms 667576 KB Output is correct
26 Correct 824 ms 661260 KB Output is correct
27 Correct 472 ms 218436 KB Output is correct
28 Correct 736 ms 221156 KB Output is correct
29 Correct 623 ms 68804 KB Output is correct