Submission #1154966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154966		lto5	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	132 ms	106492 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

namespace std {
#ifndef LOCAL
#define cerr \
  if (0) cerr
#endif
}  // namespace std

char mp[256];

struct TrieNode {
  int cnt;
  int child[4];
  TrieNode() {
    cnt = 0;
    memset(child, 0, sizeof(child));
  }
};

struct Trie {
  TrieNode trie[2000005];
  int tin[2000005];
  int tout[2000005];
  int timeDFS = 0;
  int numNode = 0;
  Trie() {}
  void add(string s) {
    int u = 0;
    for (char c : s) {
      c = mp[c];
      if (trie[u].child[c] == 0) {
        trie[u].child[c] = ++numNode;
      }
      u = trie[u].child[c];
    }
    trie[u].cnt++;
  }
  void dfs(int u) {
    tin[u] = ++timeDFS;
    for (int i = 0; i < 4; i++) {
      if (trie[u].child[i]) {
        dfs(trie[u].child[i]);
      }
    }
    tout[u] = timeDFS;
  }
};

struct Fen {
  int ft[2000005];
  Fen() { memset(ft, 0, sizeof(ft)); }
  void add(int x, int delta) {
    for (; x <= 2e6; x += x & -x) ft[x] += delta;
  }
  int get(int x) {
    int ans = 0;
    for (; x > 0; x -= x & -x) ans += ft[x];
    return ans;
  }
};

Trie pref, suff;
int node_pref[100005];
int node_suff[100005];

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL
#define task ""
#else
#define task "RNA"
#endif
  if (fopen(task ".inp", "r")) {
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
  }
  mp['G'] = 0;
  mp['U'] = 1;
  mp['A'] = 2;
  mp['C'] = 3;
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    pref.add(s);
    {
      int u = 0;
      for (char c : s) {
        c = mp[c];
        u = pref.trie[u].child[c];
      }
      node_pref[i] = u;
    }
    reverse(s.begin(), s.end());
    suff.add(s);
    {
      int u = 0;
      for (char c : s) {
        c = mp[c];
        u = suff.trie[u].child[c];
      }
      node_suff[i] = u;
    }
  }
  pref.dfs(0);
  suff.dfs(0);
  vector<array<int, 5>> que;
  vector<int> ans(m);
  for (int i = 0; i < m; i++) {
    string pre, suf;
    cin >> pre >> suf;
    [&]() {
      int pref_node = 0;
      for (char& c : pre) {
        c = mp[c];
        pref_node = pref.trie[pref_node].child[c];
        if (!pref_node) {
          return;
        }
      }
      reverse(suf.begin(), suf.end());
      int suf_node = 0;
      for (char& c : suf) {
        c = mp[c];
        suf_node = suff.trie[suf_node].child[c];
        if (!suf_node) {
          return;
        }
      }
      // tin[pref_node] <= tin[node_pref[i]] <= tout[pref_node]
      // tin[suff_node] <= tin[node_suff[i]] <= tout[suff_node]
      que.push_back({pref.tin[pref_node] - 1, -1, suff.tin[suf_node], suff.tout[suf_node], i});
      que.push_back({pref.tout[pref_node], 1, suff.tin[suf_node], suff.tout[suf_node], i});
    }();
  }
  for (int i = 1; i <= n; i++) {
    que.push_back({pref.tin[node_pref[i]], -2, suff.tin[node_suff[i]], -1, -1});
  }
  sort(que.begin(), que.end());
  Fen fen;
  for (auto [_, delta, l, r, i] : que) {
    if (delta == -2) {
      fen.add(l, 1);
    } else {
      ans[i] += delta * (fen.get(r) - fen.get(l - 1));
    }
  }
  for (auto it : ans) cout << it << '\n';
  return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:78:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     freopen(task ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:79:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     freopen(task ".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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