Submission #1230174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230174		hiderr	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	233 ms	231328 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

#define loop(i, a, b) for(int i = a; i <= b; i++)
#define loop_rev(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define pb push_back

using ll = long long;

struct TreeNode {
  int l = 0, r = 0, sum = 0;
};

const int TREE_BASE = (1 << 18);
const int MAX_N = 100'000;

TreeNode st_pool[MAX_N * 18 + 1'000];
int st_node() {
  static int node_id = 0;
  return ++node_id;
}

struct SegTree {
  int root = 0;
  void update(int i, int val, int& v, int l, int r) {
    if(v == 0) v = st_node();
    st_pool[v].sum += val;
    if(l != r) {
      int mid = (l + r) / 2;
      if(i <= mid) update(i, val, st_pool[v].l, l, mid);
      else update(i, val, st_pool[v].r, mid + 1, r);
    }
  }
  void update(int i, int val) {
    update(i, val, root, 0, TREE_BASE - 1);
  }
  int query(int a, int b, int v, int l, int r) {
    if(v == 0) return 0;
    if(l >= a && r <= b) {
      return st_pool[v].sum;
    }
    int mid = (l + r) / 2, res = 0;
    if(a <= mid) {
      res += query(a, b, st_pool[v].l, l, mid); // BUG FOUND: Quadratic query (l <= mid instead of a <= mid)
    }
    if(b > mid) {
      res += query(a, b, st_pool[v].r, mid + 1, r);
    }
    return res;
  }
  int query(int a, int b) {
    return query(a, b, root, 0, TREE_BASE - 1);
  }
  void include(int &v_this, int v_other) {
    if(v_other == 0) return;
    if(v_this == 0) { v_this = v_other; return; }
    if(st_pool[v_other].l)
      include(st_pool[v_this].l, st_pool[v_other].l);
    if(st_pool[v_other].r)
      include(st_pool[v_this].r, st_pool[v_other].r);
    st_pool[v_this].sum = st_pool[st_pool[v_this].l].sum + st_pool[st_pool[v_this].r].sum;
  }
  void include_disjoint_segtree(SegTree& other) {
    include(root, other.root);
  }
};

struct TrieNode {
  int ptr[4];
  vector<int> values;
  int tin = 0, tout = 0;
  SegTree st;
};

const int MAX_LEN = 2'000'000;
TrieNode trie_pool[2 * MAX_LEN + 1'000];
int trie_node() {
  static int node_id = 0;
  return ++node_id;
}

struct Trie {
  int root = trie_node();
  int insert(string const& s, int value) {
    int v = root;
    loop(i, 0, sz(s) - 1) {
      int& dest = trie_pool[v].ptr[s[i] - 'a'];
      if(!dest) dest = trie_node();
      v = dest;
    }
    trie_pool[v].values.pb(value);
    return v;
  }
  int find(string const& s) {
    int v = root;
    loop(i, 0, sz(s) - 1) {
      if(!v) return 0;
      int& dest = trie_pool[v].ptr[s[i] - 'a'];
      v = dest;
    }
    return v;
  }
  void euler_tour() {
    int timer = 1;
    _euler_tour(root, timer);
  }
  void _euler_tour(int v, int& timer) {
    int cnt = 0; for(int s : trie_pool[v].ptr) cnt += (s != 0);
    trie_pool[v].tin = timer;
    for(int s : trie_pool[v].ptr) {
      if(!s) continue;
      if(sz(trie_pool[v].values) || cnt > 1) ++timer;
      _euler_tour(s, timer);
    }
    trie_pool[v].tout = timer;
  }
  vector<int> rev_topo() {
    vector<int> res; _rev_topo(root, res); return res;
  }
  void _rev_topo(int v, vector<int>& res) {
    for(int s : trie_pool[v].ptr) {
      if(s) _rev_topo(s, res);
    }
    res.pb(v);
  }
};

void F(string& s) { for(char& c : s) if(c == 'A') c = 'a'; else if(c == 'G') c = 'b'; else if(c == 'C') c = 'c'; else if(c == 'U') c = 'd'; }

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, m; cin >> n >> m;

  vector<int> trie_id(n + 1);
  vector<string> S(n + 1);

  Trie pref, suff;

  loop(i, 1, n) {
    cin >> S[i]; F(S[i]);
    trie_id[i] = pref.insert(S[i], i);
  }

  pref.euler_tour();
  
  loop(i, 1, n) {
    reverse(all(S[i]));
    suff.insert(S[i], i);
  }

  vector<int> res(m + 1);
  vector<int> id_p(m + 1);

  auto order = suff.rev_topo();

  loop(i, 1, m) {
    string p, q; cin >> p >> q; F(p), F(q);
    id_p[i] = pref.find(p);
    reverse(all(q)); int id_q = suff.find(q);
    if(id_q != 0) {
      trie_pool[id_q].values.pb(-i);
    }
  }

  for(int v : order) {
    for(int s : trie_pool[v].ptr) {
      if(s) trie_pool[v].st.include_disjoint_segtree(trie_pool[s].st);
    }
    for(int val : trie_pool[v].values) {
      if(val > 0) {
        trie_pool[v].st.update(trie_pool[trie_id[val]].tin, 1);
      }
      else {
        int q_ind = (-val), pref_id = id_p[q_ind];
        if(pref_id != 0) res[q_ind] = trie_pool[v].st.query(trie_pool[pref_id].tin, trie_pool[pref_id].tout);
      }
    }
  }

  loop(i, 1, m) {
    cout << res[i] << '\n';
  }

}

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