oj.uz

Submission #332747

# Submission time Handle Problem Language Result Execution time Memory
332747 2020-12-03T06:10:00 Z casperwang Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 427 ms 297580 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*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

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 174 ms 282348 KB Output is correct
2 Correct 176 ms 282220 KB Output is correct
3 Correct 177 ms 282348 KB Output is correct
4 Correct 172 ms 282220 KB Output is correct
5 Correct 173 ms 282220 KB Output is correct
6 Correct 174 ms 282304 KB Output is correct
7 Correct 172 ms 282220 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 282920 KB Output is correct
2 Correct 267 ms 283136 KB Output is correct
3 Correct 265 ms 282988 KB Output is correct
4 Correct 264 ms 283244 KB Output is correct
5 Correct 295 ms 283116 KB Output is correct
6 Correct 298 ms 283244 KB Output is correct
7 Correct 212 ms 282988 KB Output is correct
8 Correct 288 ms 283116 KB Output is correct
9 Correct 275 ms 283244 KB Output is correct
10 Correct 240 ms 282988 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 288740 KB Output is correct
2 Correct 234 ms 286156 KB Output is correct
3 Correct 230 ms 287852 KB Output is correct
4 Correct 207 ms 286956 KB Output is correct
5 Correct 209 ms 286176 KB Output is correct
6 Correct 220 ms 287852 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 282348 KB Output is correct
2 Correct 176 ms 282220 KB Output is correct
3 Correct 177 ms 282348 KB Output is correct
4 Correct 172 ms 282220 KB Output is correct
5 Correct 173 ms 282220 KB Output is correct
6 Correct 174 ms 282304 KB Output is correct
7 Correct 172 ms 282220 KB Output is correct
8 Correct 270 ms 282920 KB Output is correct
9 Correct 267 ms 283136 KB Output is correct
10 Correct 265 ms 282988 KB Output is correct
11 Correct 264 ms 283244 KB Output is correct
12 Correct 295 ms 283116 KB Output is correct
13 Correct 298 ms 283244 KB Output is correct
14 Correct 212 ms 282988 KB Output is correct
15 Correct 288 ms 283116 KB Output is correct
16 Correct 275 ms 283244 KB Output is correct
17 Correct 240 ms 282988 KB Output is correct
18 Correct 220 ms 288740 KB Output is correct
19 Correct 234 ms 286156 KB Output is correct
20 Correct 230 ms 287852 KB Output is correct
21 Correct 207 ms 286956 KB Output is correct
22 Correct 209 ms 286176 KB Output is correct
23 Correct 220 ms 287852 KB Output is correct
24 Correct 283 ms 286444 KB Output is correct
25 Correct 292 ms 288364 KB Output is correct
26 Correct 265 ms 285804 KB Output is correct
27 Correct 287 ms 286444 KB Output is correct
28 Correct 427 ms 297580 KB Output is correct
29 Correct 308 ms 297324 KB Output is correct