oj.uz

Submission #668617

# Submission time Handle Problem Language Result Execution time Memory
668617 2022-12-04T09:24:24 Z Shin Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 201 ms 151384 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

struct fenwick_tree {
  vector<int> bit;
  int n;
  fenwick_tree(int _n) : n(_n) {
    bit.assign(n + 7, 0);
  }
  int get(int i) const {
    int res = 0;
    for (i ++, minimize(i, n); i > 0; i -= i & -i) res += bit[i];
    return res;
  }
  int get_range(int l, int r) const {
    if (r < l) return 0;
    return get(r) - get(l - 1);
  }
  
  void modify(int i, int v) {
    for (++ i; i <= n; i += i & -i) bit[i] += v;
  }
};

const char base[] = {'A', 'G', 'C', 'U'};
struct Trie {
  const static int M = 2e6 + 100;
  int node[M][4];
  int num_node;
  int ind[26];
  int cnt[M];
  int tin[M];
  int tout[M];

  auto & operator [](int i) { 
    return node[i]; 
  }

  const auto & operator [](int i) const { 
    return node[i]; 
  }

  Trie() {
    memset(node, 0, sizeof node);
    num_node = 0;
    for (int i = 0; i < 4; i ++) {
      ind[base[i] - 'A'] = i;
    }
  }

  int add(string &s) {
    int cur = 0;
    for (int i = 0; i < (int) s.size(); i ++) {
      int c = ind[s[i] - 'A'];
      if (node[cur][c] == 0) {
        node[cur][c] = ++ num_node;
      }
      cur = node[cur][c];
    }
    cnt[cur] ++;
    return cur;
  }

  int find_str(string &s) {
    int cur = 0;
    for (int i = 0; i < (int) s.size(); i ++) {
      int c = ind[s[i] - 'A'];
      if (node[cur][c] == 0) {
        return - 1;
      }
      cur = node[cur][c];
    }
    return cur;
  }

  void dfs_pre(int u = 0) {
    static int timer = 0;
    tin[u] = ++ timer;
    for (int i = 0; i < 4; i ++) if (node[u][i]) {
      dfs_pre(node[u][i]);
    }
    tout[u] = timer;
  }
} pref, suff;

const int N = 2e6 + 100;
int pos[N];
int res[N];
int rem[N];
vector<pair<int, int>> qr[N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, m; cin >> n >> m;
  for (int i = 1; i <= n; i ++) {
    string s; cin >> s;
    int u = pref.add(s);
    reverse(s.begin(), s.end());
    int v = suff.add(s);
    pos[u] = v;
  }
  pref.dfs_pre();
  suff.dfs_pre();
  for (int i = 1; i <= m; i ++) {
    string p, q; cin >> p >> q;
    reverse(q.begin(), q.end());
    int u = pref.find_str(p);
    int v = suff.find_str(q);
    if (u < 0 || v < 0) {
      continue;
    }
    qr[u].emplace_back(v, i);
  }

  fenwick_tree f(N);
  function<void(int)> dfs = [&](int u) {
    for (auto [v, i]: qr[u]) {
      rem[i] = f.get_range(suff.tin[v], suff.tout[v]);
    }
    f.modify(suff.tin[pos[u]], pref.cnt[u]);
    for (int i = 0; i < 4; i ++) if (pref.node[u][i]) {
      dfs(pref.node[u][i]);
    }
    for (auto [v, i]: qr[u]) {
      res[i] = f.get_range(suff.tin[v], suff.tout[v]);
    }
  };

  dfs(0);
  for (int i = 1; i <= m; i ++) {
    cout << res[i] - rem[i] << '\n';
  }
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 117708 KB Output is correct
2 Correct 50 ms 117764 KB Output is correct
3 Correct 50 ms 117820 KB Output is correct
4 Correct 53 ms 117800 KB Output is correct
5 Correct 48 ms 117752 KB Output is correct
6 Correct 48 ms 117784 KB Output is correct
7 Correct 48 ms 117724 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 138284 KB Output is correct
2 Correct 121 ms 139436 KB Output is correct
3 Correct 201 ms 145148 KB Output is correct
4 Correct 186 ms 145736 KB Output is correct
5 Incorrect 196 ms 151384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 119076 KB Output is correct
2 Correct 59 ms 118604 KB Output is correct
3 Correct 67 ms 118988 KB Output is correct
4 Correct 57 ms 118572 KB Output is correct
5 Correct 61 ms 118628 KB Output is correct
6 Correct 62 ms 118648 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 117708 KB Output is correct
2 Correct 50 ms 117764 KB Output is correct
3 Correct 50 ms 117820 KB Output is correct
4 Correct 53 ms 117800 KB Output is correct
5 Correct 48 ms 117752 KB Output is correct
6 Correct 48 ms 117784 KB Output is correct
7 Correct 48 ms 117724 KB Output is correct
8 Correct 129 ms 138284 KB Output is correct
9 Correct 121 ms 139436 KB Output is correct
10 Correct 201 ms 145148 KB Output is correct
11 Correct 186 ms 145736 KB Output is correct
12 Incorrect 196 ms 151384 KB Output isn't correct
13 Halted 0 ms 0 KB -