oj.uz

Submission #668613

# Submission time Handle Problem Language Result Execution time Memory
668613 2022-12-04T09:11:59 Z Shin Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 267 ms 306476 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 ++; 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 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 47 ms 117740 KB Output is correct
3 Correct 49 ms 117692 KB Output is correct
4 Correct 50 ms 117792 KB Output is correct
5 Correct 60 ms 117816 KB Output is correct
6 Correct 48 ms 117796 KB Output is correct
7 Correct 48 ms 117708 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 138796 KB Output is correct
2 Correct 126 ms 139692 KB Output is correct
3 Correct 201 ms 145316 KB Output is correct
4 Correct 192 ms 146340 KB Output is correct
5 Runtime error 267 ms 306476 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 62 ms 118988 KB Output is correct
2 Correct 59 ms 118652 KB Output is correct
3 Correct 64 ms 118988 KB Output is correct
4 Correct 60 ms 118532 KB Output is correct
5 Correct 59 ms 118544 KB Output is correct
6 Correct 66 ms 118848 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 47 ms 117740 KB Output is correct
3 Correct 49 ms 117692 KB Output is correct
4 Correct 50 ms 117792 KB Output is correct
5 Correct 60 ms 117816 KB Output is correct
6 Correct 48 ms 117796 KB Output is correct
7 Correct 48 ms 117708 KB Output is correct
8 Correct 132 ms 138796 KB Output is correct
9 Correct 126 ms 139692 KB Output is correct
10 Correct 201 ms 145316 KB Output is correct
11 Correct 192 ms 146340 KB Output is correct
12 Runtime error 267 ms 306476 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -