Submission #332738

#	Time	Username	Problem	Language	Result	Execution time	Memory
332738		casperwang	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1604 ms	285540 KiB

selling_rna

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

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