Submission #1311454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311454		forevpurity	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	337 ms	210644 KiB

selling_rna

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

// clang-format off
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
// clang-format on

const string RNA = "AGCU";
map<char, int> to_val;
map<int, char> to_ch;

const int ALPHA = 4;

struct Trie {
  struct Node {
    int child[ALPHA];
    int count;
    int exist;
    int l, r;
    Node() {
      fill(child, child + ALPHA, -1);
      count = exist = 0;
      l = r = -1;
    }
    int& operator[](int c) { return child[c]; }
  };

  vector<Node> nodes;

  Trie() { nodes.emplace_back(); }

  void add(const string& s, int i) {
    int at = 0;
    for (char ch : s) {
      int c = to_val[ch];
      if (nodes[at][c] == -1) {
        nodes[at][c] = size(nodes);
        nodes.emplace_back();
      }
      at = nodes[at][c];
      nodes[at].count++;
      if (nodes[at].l == -1) nodes[at].l = nodes[at].r = i;
      else {
        chmin(nodes[at].l, i);
        chmax(nodes[at].r, i);
      }
    }
    nodes[at].exist++;
  }

  pii get_range(const string& s) {
    int at = 0;
    pii res = {-1, -1};
    for (char ch : s) {
      int c = to_val[ch];
      if (nodes[at][c] == -1) return res;
      at = nodes[at][c];
    }
    if (at != -1) res = {nodes[at].l, nodes[at].r};
    return res;
  }

  void dfs(int at, string& c_str, vector<string>& ve) {
    for (int i = 0; i < nodes[at].exist; i++) ve.pb(c_str);

    for (int i = 0; i < 4; i++) {
      if (int to = nodes[at][i]; to != -1) {
        c_str.push_back(to_ch[i]);
        dfs(to, c_str, ve);
        c_str.pop_back();
      }
    }
  }

  vector<string> sort_str() {
    vector<string> ve;
    string c_str = "";
    dfs(0, c_str, ve);
    return ve;
  }
};

struct RTrie {
  struct Node {
    int child[ALPHA];
    int count;
    int exist;
    vector<int> idx;
    Node() {
      fill(child, child + ALPHA, -1);
      count = exist = 0;
    }
    int& operator[](int c) { return child[c]; }
  };

  vector<Node> nodes;

  RTrie() { nodes.emplace_back(); }

  void add(const string& s, int i) {
    int at = 0;
    for (char ch : s) {
      int c = to_val[ch];
      if (nodes[at][c] == -1) {
        nodes[at][c] = size(nodes);
        nodes.emplace_back();
      }
      at = nodes[at][c];
      nodes[at].count++;
      nodes[at].idx.pb(i);
    }
    nodes[at].exist++;
  }

  int query(string& s, pii range) {
    int at = 0;
    int res = 0;
    for (char ch : s) {
      int c = to_val[ch];
      at = nodes[at][c];
      if (at == -1) return res;
    }

    vector ve(all(nodes[at].idx));

    int l = lower_bound(all(ve), range.fi) - ve.begin();
    int r = upper_bound(all(ve), range.se) - ve.begin();
    res = r - l;

    return res;
  }
};

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

  // 古力娜扎

  for (int i = 0; i < 4; i++) to_val[RNA[i]] = i;
  for (int i = 0; i < 4; i++) to_ch[i] = RNA[i];

  int n, m;
  cin >> n >> m;

  Trie sort_tr;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    sort_tr.add(s, 0);
  }

  vector<string> ve = sort_tr.sort_str();

  Trie tr;
  RTrie r_tr;

  for (int i = 0; i < n; i++) tr.add(ve[i], i);
  for (int i = 0; i < n; i++) {
    reverse(all(ve[i]));
    r_tr.add(ve[i], i);
  }

  for (int i = 0; i < m; i++) {
    string pr, su;
    cin >> pr >> su;
    pii range = tr.get_range(pr);
    reverse(all(su));
    int res = r_tr.query(su, range);
    cout << res << '\n';
  }

  return 0;
}

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