Submission #332747

#	Time	Username	Problem	Language	Result	Execution time	Memory
332747		casperwang	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	427 ms	297580 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 BLOCK = 300;
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;

struct Qry{
  int l, r, id;
  Qry() {}
  Qry(int _l, int _r, int _id) {
    l = _l, r = _r, id = _id;
  }
} qry[MAXN];

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;

class Seg{
  private:
    int arr[MAXN*4+1];
    void pull(int now) {
      arr[now] = arr[now*2] + arr[now*2+1];
    }
  public:
    void mdy(int p, int v, int now=1, int l=1, int r=n) {
      if (l == p && r == p) {
        arr[now] += v;
        return;
      } else if (l > p || r < p) return;
      int mid = l + r >> 1;
      mdy(p, v, now*2  , l, mid);
      mdy(p, v, now*2+1,mid+1,r);
      pull(now);
    }
    int qry(int ql, int qr, int now=1, int l=1, int r=n) {
      if (ql <= l && r <= qr) {
        return arr[now];
      } else if (l > qr || r < ql) return 0;
      int mid = l + r >> 1, sum = 0;
      sum += qry(ql, qr, now*2  , l, mid);
      sum += qry(ql, qr, now*2+1,mid+1,r);
      return sum;
    }
} seg;

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);
  int tmp[MAXN+1];
  for (int i = 1; i <= n; i++)
    tmp[pre_arr[i]] = i;
  for (int i = 1; i <= n; i++)
    suf_arr[i] = tmp[suf_arr[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);
    qry[i-1] = Qry(suf_ran[i].ff, suf_ran[i].ss, i);
  }
  sort(qry, qry+m, [](const Qry a, const Qry b) {
    return (a.l / BLOCK != b.l / BLOCK) ? a.l < b.l : a.r < b.r;
  });
  int nowL = 1, nowR = 0;
  for (int i = 0; i < m; i++) {
    int id = qry[i].id;
    while (nowR < qry[i].r) 
      seg.mdy(suf_arr[++nowR], 1);
    while (nowL > qry[i].l)
      seg.mdy(suf_arr[--nowL], 1);
    while (nowR > qry[i].r)
      seg.mdy(suf_arr[nowR--], -1);
    while (nowL < qry[i].l)
      seg.mdy(suf_arr[nowL++], -1);
    ans[id] = seg.qry(pre_ran[id].ff, pre_ran[id].ss);
  }
  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:41: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]
   41 |       for (int i = 0; i < s.size(); i++) {
      |                       ~~^~~~~~~~~~
selling_rna.cpp:42:31: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |         if (!arr[now].c[P[s[i]]])
      |                               ^
selling_rna.cpp:43:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |           arr[now].c[P[s[i]]] = ++cnt;
      |                            ^
selling_rna.cpp:44:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   44 |         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:60: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]
   60 |       for (int i = 0; i < s.size(); i++) {
      |                       ~~^~~~~~~~~~
selling_rna.cpp:61:31: warning: array subscript has type 'char' [-Wchar-subscripts]
   61 |         if (!arr[now].c[P[s[i]]]) {
      |                               ^
selling_rna.cpp:65:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   65 |         now = arr[now].c[P[s[i]]];
      |                                ^
selling_rna.cpp: In member function 'void Seg::mdy(long long int, long long int, long long int, long long int, long long int)':
selling_rna.cpp:84:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |       int mid = l + r >> 1;
      |                 ~~^~~
selling_rna.cpp: In member function 'long long int Seg::qry(long long int, long long int, long long int, long long int, long long int)':
selling_rna.cpp:93:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |       int mid = l + r >> 1, sum = 0;
      |                 ~~^~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40