oj.uz

Submission #668611

# Submission time Handle Problem Language Result Execution time Memory
668611 2022-12-04T09:08:26 Z Shin Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 274 ms 308800 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 > 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) {
    if (i == 0) {
      return;
    }
    for (; i <= n; i += i & -i) bit[i] += v;
  }
};

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

  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 + 7;
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[u][i]) {
      dfs(pref[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 48 ms 117708 KB Output is correct
2 Correct 48 ms 117804 KB Output is correct
3 Correct 48 ms 117732 KB Output is correct
4 Correct 52 ms 117788 KB Output is correct
5 Correct 51 ms 117788 KB Output is correct
6 Correct 59 ms 117704 KB Output is correct
7 Correct 52 ms 117716 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 140072 KB Output is correct
2 Correct 128 ms 141096 KB Output is correct
3 Correct 202 ms 146904 KB Output is correct
4 Correct 192 ms 148960 KB Output is correct
5 Runtime error 274 ms 308800 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 119436 KB Output is correct
2 Correct 63 ms 119116 KB Output is correct
3 Correct 83 ms 119372 KB Output is correct
4 Correct 62 ms 118856 KB Output is correct
5 Correct 61 ms 118896 KB Output is correct
6 Correct 67 ms 119188 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 117708 KB Output is correct
2 Correct 48 ms 117804 KB Output is correct
3 Correct 48 ms 117732 KB Output is correct
4 Correct 52 ms 117788 KB Output is correct
5 Correct 51 ms 117788 KB Output is correct
6 Correct 59 ms 117704 KB Output is correct
7 Correct 52 ms 117716 KB Output is correct
8 Correct 127 ms 140072 KB Output is correct
9 Correct 128 ms 141096 KB Output is correct
10 Correct 202 ms 146904 KB Output is correct
11 Correct 192 ms 148960 KB Output is correct
12 Runtime error 274 ms 308800 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -