Submission #599142

#	Time	Username	Problem	Language	Result	Execution time	Memory
599142		piOOE	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	141 ms	71780 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int inf = 1e9;

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

struct node {
  int sz = 0, mn = inf, mx = -inf, go[4] = {-1, -1, -1, -1};

  node() = default;
};

vector<node> t = {{}};

void add(string &str, int key) {
  int v = 0;
  for (int i = 0; i < (int) str.size(); ++i) {
    int c = str[i] - 'a';
    if (t[v].go[c] == -1) {
      t.emplace_back();
      t[v].go[c] = (int) t.size() - 1;
    }
    t[v].sz += 1;
    t[v].mn = min(t[v].mn, key);
    t[v].mx = max(t[v].mx, key);
    v = t[v].go[c];
  }
  t[v].sz += 1;
  t[v].mn = min(t[v].mn, key);
  t[v].mx = max(t[v].mx, key);
}

int find(string &str) {
  int v = 0;
  for (int i = 0; i < (int) str.size() && v != -1; ++i) {
    v = t[v].go[str[i] - 'a'];
  }
  return v;
}


int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<string> s(n);
  for (int i = 0; i < n; ++i) {
    cin >> s[i];
    transform(s[i]);
  }
  sort(s.begin(), s.end());
  vector<string> a(m), b(m);
  vector<int> ans(m);
  vector<vector<pair<int, int>>> qu(n);
  for (int i = 0; i < m; ++i) {
    cin >> a[i] >> b[i];
    transform(a[i]), transform(b[i]);
    reverse(b[i].begin(), b[i].end());
  }
  for (int i = 0; i < n; ++i) {
    add(s[i], i);
  }
  for (int i = 0; i < m; ++i) {
    int v = find(a[i]);
    if (v == -1) {
      continue;
    }
    assert(t[v].sz == t[v].mx - t[v].mn + 1);
    if (t[v].mn > 0) {
      qu[t[v].mn - 1].emplace_back(i, -1);
    }
    qu[t[v].mx].emplace_back(i, 1);
  }
  t = {{}};
  for (int i = 0; i < n; ++i) {
    reverse(s[i].begin(), s[i].end());
    add(s[i], i);
    for (auto [j, k] : qu[i]) {
      int v = find(b[j]);
      if (v != -1) {
        ans[j] += k * t[v].sz;
      }
    }
  }
  for (int i = 0; i < m; ++i) {
    cout << ans[i] << '\n';
  }
  return 0;
}

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