oj.uz

Submission #332738

# Submission time Handle Problem Language Result Execution time Memory
332738 2020-12-03T05:45:31 Z casperwang Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 285540 KB 
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;

const int MAXN = 100000;
const int MOD = 998244353;
const int K = 10;
int n, m;
int P[200];
int pre_arr[MAXN+1];
int suf_arr[MAXN+1];
pii pre_ran[MAXN+1];
pii suf_ran[MAXN+1];
int pos[MAXN+1];
int ans[MAXN];
string s, p, q;
int cc;

class Trie{
  private:
    struct node{
      int c[4];
      vector <int> id;
      int l, r;
    } arr[MAXN*20+1];
    int cnt;
  public:
    void add(string &s, int id) {
      int now = 0;
      for (int i = 0; i < s.size(); i++) {
        if (!arr[now].c[P[s[i]]])
          arr[now].c[P[s[i]]] = ++cnt;
        now = arr[now].c[P[s[i]]];
      }
      arr[now].id.pb(id);
    }
    void dfs(int now, int A[]) {
      arr[now].l = cc+1;
      for (int i = 0; i < 4; i++) {
        if (!arr[now].c[i]) continue;
        dfs(arr[now].c[i], A);
      }
      for (int i : arr[now].id)
        A[++cc] = i;
      arr[now].r = cc;
    }
    void tag(string &s, int id, pii A[]) {
      int now = 0;
      for (int i = 0; i < s.size(); i++) {
        if (!arr[now].c[P[s[i]]]) {
          now = 0;
          break;
        }
        now = arr[now].c[P[s[i]]];
      }
      if (now)
        A[id] = pii(arr[now].l, arr[now].r);
    }
} pre, suf;

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  P['A'] = 0, P['U'] = 1, P['C'] = 2, P['G'] = 3;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> s;
    pre.add(s, i);
    reverse(s.begin(), s.end());
    suf.add(s, i);
  }
  cc = 0;
  pre.dfs(0, pre_arr);
  cc = 0;
  suf.dfs(0, suf_arr);
  for (int i = 1; i <= n; i++)
    pos[suf_arr[i]] = i;
  for (int i = 1; i <= m; i++) {
    cin >> p >> q;
    pre.tag(p, i, pre_ran);
    reverse(q.begin(), q.end());
    suf.tag(q, i, suf_ran);
    for (int j = pre_ran[i].ff; j <= pre_ran[i].ss; j++) {
      if (pos[pre_arr[j]] >= suf_ran[i].ff && pos[pre_arr[j]] <= suf_ran[i].ss)
        ans[i]++;
    }
  }
  for (int i = 1; i <= m; i++)
    cout << ans[i] << '\n';
  return 0;
}

Compilation message

selling_rna.cpp: In member function 'void Trie::add(std::string&, long long int)':
selling_rna.cpp:34:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |       for (int i = 0; i < s.size(); i++) {
      |                       ~~^~~~~~~~~~
selling_rna.cpp:35:31: warning: array subscript has type 'char' [-Wchar-subscripts]
   35 |         if (!arr[now].c[P[s[i]]])
      |                               ^
selling_rna.cpp:36:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   36 |           arr[now].c[P[s[i]]] = ++cnt;
      |                            ^
selling_rna.cpp:37:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   37 |         now = arr[now].c[P[s[i]]];
      |                                ^
selling_rna.cpp: In member function 'void Trie::tag(std::string&, long long int, std::pair<long long int, long long int>*)':
selling_rna.cpp:53:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |       for (int i = 0; i < s.size(); i++) {
      |                       ~~^~~~~~~~~~
selling_rna.cpp:54:31: warning: array subscript has type 'char' [-Wchar-subscripts]
   54 |         if (!arr[now].c[P[s[i]]]) {
      |                               ^
selling_rna.cpp:58:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   58 |         now = arr[now].c[P[s[i]]];
      |                                ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 282220 KB Output is correct
2 Correct 147 ms 282220 KB Output is correct
3 Correct 152 ms 282220 KB Output is correct
4 Correct 147 ms 282176 KB Output is correct
5 Correct 144 ms 282220 KB Output is correct
6 Correct 148 ms 282220 KB Output is correct
7 Correct 148 ms 282220 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 282752 KB Output is correct
2 Correct 288 ms 282988 KB Output is correct
3 Correct 245 ms 282860 KB Output is correct
4 Correct 250 ms 282860 KB Output is correct
5 Correct 267 ms 282860 KB Output is correct
6 Correct 273 ms 282860 KB Output is correct
7 Correct 198 ms 282604 KB Output is correct
8 Correct 259 ms 282860 KB Output is correct
9 Correct 243 ms 282860 KB Output is correct
10 Correct 285 ms 282732 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1604 ms 285540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 282220 KB Output is correct
2 Correct 147 ms 282220 KB Output is correct
3 Correct 152 ms 282220 KB Output is correct
4 Correct 147 ms 282176 KB Output is correct
5 Correct 144 ms 282220 KB Output is correct
6 Correct 148 ms 282220 KB Output is correct
7 Correct 148 ms 282220 KB Output is correct
8 Correct 260 ms 282752 KB Output is correct
9 Correct 288 ms 282988 KB Output is correct
10 Correct 245 ms 282860 KB Output is correct
11 Correct 250 ms 282860 KB Output is correct
12 Correct 267 ms 282860 KB Output is correct
13 Correct 273 ms 282860 KB Output is correct
14 Correct 198 ms 282604 KB Output is correct
15 Correct 259 ms 282860 KB Output is correct
16 Correct 243 ms 282860 KB Output is correct
17 Correct 285 ms 282732 KB Output is correct
18 Execution timed out 1604 ms 285540 KB Time limit exceeded
19 Halted 0 ms 0 KB -