oj.uz

Submission #118730

# Submission time Handle Problem Language Result Execution time Memory
118730 2019-06-19T14:16:21 Z IOrtroiii Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 921 ms 696316 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[257 * N];
int r[257 * N];
int sz[257 * N];
int nxt[257 * 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 5 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 5 ms 3584 KB Output is correct
6 Correct 5 ms 3584 KB Output is correct
7 Correct 4 ms 3584 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 733 ms 652944 KB Output is correct
2 Correct 819 ms 696316 KB Output is correct
3 Correct 471 ms 231100 KB Output is correct
4 Correct 430 ms 225940 KB Output is correct
5 Correct 663 ms 489080 KB Output is correct
6 Correct 683 ms 496244 KB Output is correct
7 Correct 205 ms 87544 KB Output is correct
8 Correct 624 ms 477816 KB Output is correct
9 Correct 522 ms 420984 KB Output is correct
10 Correct 424 ms 312876 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 12536 KB Output is correct
2 Correct 89 ms 13216 KB Output is correct
3 Correct 112 ms 13180 KB Output is correct
4 Correct 93 ms 11640 KB Output is correct
5 Correct 90 ms 11964 KB Output is correct
6 Correct 112 ms 12612 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 5 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 5 ms 3584 KB Output is correct
6 Correct 5 ms 3584 KB Output is correct
7 Correct 4 ms 3584 KB Output is correct
8 Correct 733 ms 652944 KB Output is correct
9 Correct 819 ms 696316 KB Output is correct
10 Correct 471 ms 231100 KB Output is correct
11 Correct 430 ms 225940 KB Output is correct
12 Correct 663 ms 489080 KB Output is correct
13 Correct 683 ms 496244 KB Output is correct
14 Correct 205 ms 87544 KB Output is correct
15 Correct 624 ms 477816 KB Output is correct
16 Correct 522 ms 420984 KB Output is correct
17 Correct 424 ms 312876 KB Output is correct
18 Correct 123 ms 12536 KB Output is correct
19 Correct 89 ms 13216 KB Output is correct
20 Correct 112 ms 13180 KB Output is correct
21 Correct 93 ms 11640 KB Output is correct
22 Correct 90 ms 11964 KB Output is correct
23 Correct 112 ms 12612 KB Output is correct
24 Correct 816 ms 663332 KB Output is correct
25 Correct 921 ms 663416 KB Output is correct
26 Correct 816 ms 657400 KB Output is correct
27 Correct 476 ms 214440 KB Output is correct
28 Correct 685 ms 216796 KB Output is correct
29 Correct 407 ms 65500 KB Output is correct