oj.uz

Submission #730406

# Submission time Handle Problem Language Result Execution time Memory
730406 2023-04-25T20:06:43 Z jampm Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 244 ms 243824 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define all(a) a.begin(), a.end()
const int Mxn = 6e6 + 1, mxn = 1e5 + 1;

int get(char c) {
  if (c == 'A') return 0;
  if (c == 'G') return 1;
  if (c == 'U') return 2;
  return 3;
}
struct Tnode {
  Tnode * ch[4];
  vector<int> vals;
  int tin, tout;
  Tnode() {
    for (int i = 0; i < 4; i++) ch[i] = NULL;
  }
  bool exists(int x) {return ch[x] != NULL;}
  void safe(int x) {if (!exists(x)) ch[x] = new Tnode;}
};

void insert(string s, int idx, Tnode * node) {
  for (auto e : s) {
    node->safe(get(e)); node = node->ch[get(e)];
  }
  node->vals.push_back(idx);
}

pii search(string s, Tnode * node) {
  pii A = {-1, -1};
  for (auto e : s) {
    if (!node->exists(get(e))) return A;
    node = node->ch[get(e)];
  }
  return {node->tin, node->tout};
}

int tin[2][mxn], cnt = 1;

void dfs(Tnode * node, int idx = 0) {
  for (auto e : node->vals) tin[idx][e] = cnt;
  node->tin = cnt++;
  for (int i = 0; i < 4; i++) {
    if (node->exists(i)) dfs(node->ch[i], idx);
  }
  node->tout = cnt++;
}

struct SegTree {
  vector<int> segs;
  SegTree() {segs.assign(Mxn<<1, 0);}
  void upd(int i, int x) {
    segs[i += Mxn] += x;
    for (i >>= 1; i; i >>= 1) {
      segs[i] = segs[i<<1] + segs[i<<1|1];
    }
  }
  int query(int l, int r, int ans = 0) {
    for (l += Mxn, r += Mxn + 1; l < r; l >>= 1, r >>= 1) {
      if (l&1) ans += segs[l++];
      if (r&1) ans += segs[--r];
    }
    return ans;
  }
};
struct event {
  int type, v, a, b, idx;
  bool operator<(const event & A) {
    return ((v == A.v) ? type < A.type : v < A.v);
  }
};
vector<event> V;
int Ans[mxn];


int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, m; cin >> n >> m;
  string s, p;
  Tnode * Pre = new Tnode;
  Tnode * Suf = new Tnode;
  for (int i = 0; i < n; i++) {
    cin >> s; 
    insert(s, i, Pre);
    reverse(all(s));
    insert(s, i, Suf);
  }
  dfs(Pre, 0), cnt = 1, dfs(Suf, 1);
  for (int i = 0; i < n; i++) {
    V.push_back({0, tin[0][i], tin[1][i], 0, 0});
  }
  pii dummy = {-1, -1};
  for (int i = 0; i < m; i++) {
    Ans[i] = 0;
    cin >> p >> s;
    reverse(all(s));
    pii X = search(p, Pre), Y = search(s, Suf);
    if (X == dummy || Y == dummy) continue;
    V.push_back({2, X.first - 1, Y.first, Y.second, i});
    V.push_back({1, X.second, Y.first, Y.second, i});
  }
  sort(all(V)); SegTree segs;
  for (auto [type, v, a, b, idx] : V) {
    if (type == 0) {
      segs.upd(a, 1);
    } else if (type == 1) {
      Ans[idx] += segs.query(a, b);
    } else if (type == 2) {
      Ans[idx] -= segs.query(a, b);
    }
  }
  for (int i = 0; i < m; i++) {
    cout << Ans[i] << "\n";
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47324 KB Output is correct
2 Correct 21 ms 47316 KB Output is correct
3 Correct 22 ms 47352 KB Output is correct
4 Correct 20 ms 47348 KB Output is correct
5 Correct 21 ms 47260 KB Output is correct
6 Correct 20 ms 47316 KB Output is correct
7 Correct 23 ms 47284 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 202220 KB Output is correct
2 Correct 183 ms 197948 KB Output is correct
3 Correct 185 ms 203976 KB Output is correct
4 Correct 186 ms 196640 KB Output is correct
5 Correct 244 ms 240940 KB Output is correct
6 Correct 238 ms 243824 KB Output is correct
7 Correct 59 ms 53568 KB Output is correct
8 Correct 183 ms 165636 KB Output is correct
9 Correct 146 ms 147448 KB Output is correct
10 Correct 116 ms 142268 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 51708 KB Output is correct
2 Correct 45 ms 50436 KB Output is correct
3 Correct 48 ms 51020 KB Output is correct
4 Correct 39 ms 50244 KB Output is correct
5 Correct 44 ms 50392 KB Output is correct
6 Correct 47 ms 51084 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47324 KB Output is correct
2 Correct 21 ms 47316 KB Output is correct
3 Correct 22 ms 47352 KB Output is correct
4 Correct 20 ms 47348 KB Output is correct
5 Correct 21 ms 47260 KB Output is correct
6 Correct 20 ms 47316 KB Output is correct
7 Correct 23 ms 47284 KB Output is correct
8 Correct 190 ms 202220 KB Output is correct
9 Correct 183 ms 197948 KB Output is correct
10 Correct 185 ms 203976 KB Output is correct
11 Correct 186 ms 196640 KB Output is correct
12 Correct 244 ms 240940 KB Output is correct
13 Correct 238 ms 243824 KB Output is correct
14 Correct 59 ms 53568 KB Output is correct
15 Correct 183 ms 165636 KB Output is correct
16 Correct 146 ms 147448 KB Output is correct
17 Correct 116 ms 142268 KB Output is correct
18 Correct 47 ms 51708 KB Output is correct
19 Correct 45 ms 50436 KB Output is correct
20 Correct 48 ms 51020 KB Output is correct
21 Correct 39 ms 50244 KB Output is correct
22 Correct 44 ms 50392 KB Output is correct
23 Correct 47 ms 51084 KB Output is correct
24 Correct 184 ms 178816 KB Output is correct
25 Correct 222 ms 180368 KB Output is correct
26 Correct 162 ms 176836 KB Output is correct
27 Correct 179 ms 177188 KB Output is correct
28 Correct 179 ms 77028 KB Output is correct
29 Correct 95 ms 59152 KB Output is correct