oj.uz

Submission #118719

# Submission time Handle Problem Language Result Execution time Memory
118719 2019-06-19T14:11:34 Z IOrtroiii Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 931 ms 1048576 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[100 * N];
int r[100 * N];
int sz[100 * N];
int nxt[100 * 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 5 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 5 ms 3584 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 931 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 13048 KB Output is correct
2 Correct 89 ms 13616 KB Output is correct
3 Correct 108 ms 13560 KB Output is correct
4 Correct 91 ms 11960 KB Output is correct
5 Correct 88 ms 12320 KB Output is correct
6 Correct 110 ms 13004 KB Output is correct

Subtask #4
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 5 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 5 ms 3584 KB Output is correct
8 Runtime error 931 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -