oj.uz

Submission #668616

# Submission time Handle Problem Language Result Execution time Memory
668616 2022-12-04T09:23:31 Z Shin Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 261 ms 306544 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]) {
      assert(suff.tout[v] < N);
      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 47 ms 117704 KB Output is correct
2 Correct 50 ms 117768 KB Output is correct
3 Correct 48 ms 117744 KB Output is correct
4 Correct 48 ms 117744 KB Output is correct
5 Correct 47 ms 117740 KB Output is correct
6 Correct 49 ms 117716 KB Output is correct
7 Correct 48 ms 117700 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 138268 KB Output is correct
2 Correct 134 ms 139400 KB Output is correct
3 Correct 201 ms 145080 KB Output is correct
4 Correct 194 ms 146004 KB Output is correct
5 Runtime error 261 ms 306544 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 119080 KB Output is correct
2 Correct 64 ms 118780 KB Output is correct
3 Correct 64 ms 118948 KB Output is correct
4 Correct 59 ms 118540 KB Output is correct
5 Correct 60 ms 118576 KB Output is correct
6 Correct 62 ms 118652 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 117704 KB Output is correct
2 Correct 50 ms 117768 KB Output is correct
3 Correct 48 ms 117744 KB Output is correct
4 Correct 48 ms 117744 KB Output is correct
5 Correct 47 ms 117740 KB Output is correct
6 Correct 49 ms 117716 KB Output is correct
7 Correct 48 ms 117700 KB Output is correct
8 Correct 125 ms 138268 KB Output is correct
9 Correct 134 ms 139400 KB Output is correct
10 Correct 201 ms 145080 KB Output is correct
11 Correct 194 ms 146004 KB Output is correct
12 Runtime error 261 ms 306544 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -