Submission #118730

#	Time	Username	Problem	Language	Result	Execution time	Memory
118730		IOrtroiii	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	921 ms	696316 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40