oj.uz

답안 #118728

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
118728 2019-06-19T14:15:32 Z IOrtroiii Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 1008 ms 696264 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[263 * N];
int r[263 * N];
int sz[263 * N];
int nxt[263 * 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

# 결과 실행 시간 메모리 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 4 ms 3584 KB Output is correct
7 Correct 5 ms 3584 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 765 ms 652972 KB Output is correct
2 Correct 819 ms 696264 KB Output is correct
3 Correct 432 ms 231032 KB Output is correct
4 Correct 420 ms 225952 KB Output is correct
5 Correct 652 ms 489080 KB Output is correct
6 Correct 634 ms 496100 KB Output is correct
7 Correct 202 ms 87636 KB Output is correct
8 Correct 590 ms 477884 KB Output is correct
9 Correct 539 ms 421176 KB Output is correct
10 Correct 421 ms 312972 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 12536 KB Output is correct
2 Correct 89 ms 13280 KB Output is correct
3 Correct 107 ms 13176 KB Output is correct
4 Correct 88 ms 11512 KB Output is correct
5 Correct 86 ms 12056 KB Output is correct
6 Correct 109 ms 12632 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 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 4 ms 3584 KB Output is correct
7 Correct 5 ms 3584 KB Output is correct
8 Correct 765 ms 652972 KB Output is correct
9 Correct 819 ms 696264 KB Output is correct
10 Correct 432 ms 231032 KB Output is correct
11 Correct 420 ms 225952 KB Output is correct
12 Correct 652 ms 489080 KB Output is correct
13 Correct 634 ms 496100 KB Output is correct
14 Correct 202 ms 87636 KB Output is correct
15 Correct 590 ms 477884 KB Output is correct
16 Correct 539 ms 421176 KB Output is correct
17 Correct 421 ms 312972 KB Output is correct
18 Correct 120 ms 12536 KB Output is correct
19 Correct 89 ms 13280 KB Output is correct
20 Correct 107 ms 13176 KB Output is correct
21 Correct 88 ms 11512 KB Output is correct
22 Correct 86 ms 12056 KB Output is correct
23 Correct 109 ms 12632 KB Output is correct
24 Correct 858 ms 663320 KB Output is correct
25 Correct 1008 ms 663556 KB Output is correct
26 Correct 852 ms 657400 KB Output is correct
27 Correct 497 ms 214264 KB Output is correct
28 Correct 720 ms 216696 KB Output is correct
29 Correct 390 ms 65528 KB Output is correct