Submission #220163

#	Time	Username	Problem	Language	Result	Execution time	Memory
220163		rama_pang	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	865 ms	598736 KiB

selling_rna

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

void Transform(string &s) {
  for (auto &i : s) {
    if (i == 'A') i = '0';
    if (i == 'G') i = '1';
    if (i == 'C') i = '2';
    if (i == 'U') i = '3';
  }
}

class Trie {
 private:
  struct Node {
    int sz = 0;
    int nxt[4] = {-1, -1, -1, -1};
    Node() {}
  };

  vector<Node> trie = vector<Node>(1);

 public:
  Trie() {}
  vector<string> strings;

  void Insert(const string &s) {
    strings.emplace_back(s);
    int cur = 0;
    trie[cur].sz++;
    for (const auto &c : s) {
      if (trie[cur].nxt[c - '0'] == -1) {
        trie[cur].nxt[c - '0'] = trie.size();
        trie.emplace_back();
      }
      cur = trie[cur].nxt[c - '0'];
      trie[cur].sz++;
    }
  }

  int Count(const string &s) {
    int cur = 0;
    for (const auto &c : s) {
      if (cur == -1) break;
      cur = trie[cur].nxt[c - '0'];
    }
    if (cur == -1) {
      return 0;
    } else {
      return trie[cur].sz;
    }
  }

};

class SegmentTree {
 private:
  int sz;
  vector<Trie> tree;
  
 public:
  SegmentTree(const vector<string> &s) {
    sz = s.size();
    tree.resize(2 * sz);
    for (int i = 0; i < sz; i++) {
      tree[i + sz].Insert(s[i]);
    }
    for (int i = sz - 1; i > 0; i--) {
      for (const auto &j : tree[i * 2].strings) {
        tree[i].Insert(j);
      }
      for (const auto &j : tree[i * 2 + 1].strings) {
        tree[i].Insert(j);
      }
    }
  }

  int Query(int l, int r, const string &s) {
    int res = 0;
    for (l += sz, r += sz; l < r; l /= 2, r /= 2) {
      if (l & 1) res += tree[l++].Count(s);
      if (r & 1) res += tree[--r].Count(s);
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N, M;
  cin >> N >> M;

  vector<string> strings(N);
  for (int i = 0; i < N; i++) {
    cin >> strings[i];
    Transform(strings[i]);
  }

  sort(begin(strings), end(strings));
  for (int i = 0; i < N; i++) reverse(begin(strings[i]), end(strings[i]));
  SegmentTree seg(strings);
  for (int i = 0; i < N; i++) reverse(begin(strings[i]), end(strings[i]));

  for (int i = 0; i < M; i++) {
    string P, Q;
    cin >> P >> Q;

    Transform(P), Transform(Q);
    reverse(begin(Q), end(Q));

    int l = lower_bound(begin(strings), end(strings), P) - begin(strings);
    P.push_back('5');
    int r = lower_bound(begin(strings), end(strings), P) - begin(strings);
    P.pop_back();
    
    cout << seg.Query(l, r, Q) << "\n";
  }

  return 0;
}

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