Submission #668626

#	Time	Username	Problem	Language	Result	Execution time	Memory
668626		Shin	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	216 ms	159164 KiB

selling_rna

#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(suff.num_node + 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;
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40