oj.uz

Submission #332746

# Submission time Handle Problem Language Result Execution time Memory
332746 2020-12-03T06:09:01 Z casperwang Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 596 ms 584292 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 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+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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 282220 KB Output is correct
2 Correct 171 ms 282220 KB Output is correct
3 Correct 174 ms 282316 KB Output is correct
4 Correct 173 ms 282220 KB Output is correct
5 Correct 172 ms 282220 KB Output is correct
6 Correct 171 ms 282220 KB Output is correct
7 Correct 173 ms 282220 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 285036 KB Output is correct
2 Correct 273 ms 285548 KB Output is correct
3 Correct 263 ms 285292 KB Output is correct
4 Correct 277 ms 285676 KB Output is correct
5 Correct 296 ms 284652 KB Output is correct
6 Correct 303 ms 284652 KB Output is correct
7 Correct 211 ms 285420 KB Output is correct
8 Correct 286 ms 285548 KB Output is correct
9 Correct 273 ms 285680 KB Output is correct
10 Correct 242 ms 285032 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 596 ms 584292 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 282220 KB Output is correct
2 Correct 171 ms 282220 KB Output is correct
3 Correct 174 ms 282316 KB Output is correct
4 Correct 173 ms 282220 KB Output is correct
5 Correct 172 ms 282220 KB Output is correct
6 Correct 171 ms 282220 KB Output is correct
7 Correct 173 ms 282220 KB Output is correct
8 Correct 267 ms 285036 KB Output is correct
9 Correct 273 ms 285548 KB Output is correct
10 Correct 263 ms 285292 KB Output is correct
11 Correct 277 ms 285676 KB Output is correct
12 Correct 296 ms 284652 KB Output is correct
13 Correct 303 ms 284652 KB Output is correct
14 Correct 211 ms 285420 KB Output is correct
15 Correct 286 ms 285548 KB Output is correct
16 Correct 273 ms 285680 KB Output is correct
17 Correct 242 ms 285032 KB Output is correct
18 Runtime error 596 ms 584292 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -