oj.uz

Submission #668627

# Submission time Handle Problem Language Result Execution time Memory
668627 2022-12-04T09:47:43 Z Shin Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 260 ms 124860 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 + 7;
  int node[M][4];
  int num_node;
  int ind[26];
  int cnt[M];
  int tin[M];
  int tout[M];
 
  Trie() {
    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;
  }
  
  int timer = 0;
  void dfs_pre(int u = 0) {
    tin[u] = timer ++;
    for (int i = 0; i < 4; i ++) if (node[u][i]) {
      dfs_pre(node[u][i]);
    }
    tout[u] = timer - 1;
  }
} 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(suff.num_node + 1);
  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;
}

Compilation message

selling_rna.cpp: In lambda function:
selling_rna.cpp:120:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |     for (auto [v, i]: qr[u]) {
      |               ^
selling_rna.cpp:127:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  127 |     for (auto [v, i]: qr[u]) {
      |               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47316 KB Output is correct
2 Correct 22 ms 47316 KB Output is correct
3 Correct 24 ms 47316 KB Output is correct
4 Correct 23 ms 47336 KB Output is correct
5 Correct 28 ms 47292 KB Output is correct
6 Correct 23 ms 47376 KB Output is correct
7 Correct 23 ms 47308 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 106484 KB Output is correct
2 Correct 115 ms 105368 KB Output is correct
3 Correct 193 ms 105116 KB Output is correct
4 Correct 186 ms 104396 KB Output is correct
5 Correct 214 ms 123752 KB Output is correct
6 Correct 260 ms 124860 KB Output is correct
7 Correct 51 ms 47720 KB Output is correct
8 Correct 136 ms 92188 KB Output is correct
9 Correct 122 ms 84952 KB Output is correct
10 Correct 105 ms 83856 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 48524 KB Output is correct
2 Correct 34 ms 48332 KB Output is correct
3 Correct 37 ms 48536 KB Output is correct
4 Correct 33 ms 48076 KB Output is correct
5 Correct 36 ms 48188 KB Output is correct
6 Correct 37 ms 48284 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47316 KB Output is correct
2 Correct 22 ms 47316 KB Output is correct
3 Correct 24 ms 47316 KB Output is correct
4 Correct 23 ms 47336 KB Output is correct
5 Correct 28 ms 47292 KB Output is correct
6 Correct 23 ms 47376 KB Output is correct
7 Correct 23 ms 47308 KB Output is correct
8 Correct 118 ms 106484 KB Output is correct
9 Correct 115 ms 105368 KB Output is correct
10 Correct 193 ms 105116 KB Output is correct
11 Correct 186 ms 104396 KB Output is correct
12 Correct 214 ms 123752 KB Output is correct
13 Correct 260 ms 124860 KB Output is correct
14 Correct 51 ms 47720 KB Output is correct
15 Correct 136 ms 92188 KB Output is correct
16 Correct 122 ms 84952 KB Output is correct
17 Correct 105 ms 83856 KB Output is correct
18 Correct 37 ms 48524 KB Output is correct
19 Correct 34 ms 48332 KB Output is correct
20 Correct 37 ms 48536 KB Output is correct
21 Correct 33 ms 48076 KB Output is correct
22 Correct 36 ms 48188 KB Output is correct
23 Correct 37 ms 48284 KB Output is correct
24 Correct 106 ms 98376 KB Output is correct
25 Correct 117 ms 99080 KB Output is correct
26 Correct 107 ms 97468 KB Output is correct
27 Correct 169 ms 97472 KB Output is correct
28 Correct 91 ms 56384 KB Output is correct
29 Correct 60 ms 49640 KB Output is correct