Submission #516698

#	Time	Username	Problem	Language	Result	Execution time	Memory
516698		MilosMilutinovic	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	732 ms	493112 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

template <typename T>
class fenwick {
  public:
  vector<T> fenw;
  int n;
  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }
  void modify(int x, T v) {
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }
  T get(int x) {
    T v{};
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<string> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  vector<string> L(m), R(m);
  for (int i = 0; i < m; i++) {
    cin >> L[i] >> R[i];
  }
  vector<vector<int>> trie(1, vector<int>(26, -1));
  for (int i = 0; i < n; i++) {
    int t = 0;
    for (int j = 0; j < (int) s[i].size(); j++) {
      int c = (int) (s[i][j] - 'A');
      if (trie[t][c] == -1) {
        trie[t][c] = trie.size();
        trie.emplace_back(vector<int>(26, -1));
      }
      t = trie[t][c];
    }
  }
  for (int i = 0; i < m; i++) {
    int t = 0;
    for (int j = 0; j < (int) L[i].size(); j++) {
      int c = (int) (L[i][j] - 'A');
      if (trie[t][c] == -1) {
        trie[t][c] = trie.size();
        trie.emplace_back(vector<int>(26, -1));
      }
      t = trie[t][c];
    }
  }
  int k = trie.size();
  vector<int> tl(k), tr(k);
  int T;
  function<void(int)> Dfs = [&](int u) {
    tl[u] = ++T;
    for (int i = 0; i < 26; i++) {
      if (trie[u][i] != -1) {
        Dfs(trie[u][i]);
      }
    }
    tr[u] = T;
  };
  T = 0;
  Dfs(0);
  vector<int> x(n);
  vector<int> xl(m), xr(m);
  for (int i = 0; i < n; i++) {
    int t = 0;
    for (int j = 0; j < (int) s[i].size(); j++) {
      int c = (int) (s[i][j] - 'A');
      t = trie[t][c];
    }
    x[i] = tl[t];
  }
  for (int i = 0; i < m; i++) {
    int t = 0;
    for (int j = 0; j < (int) L[i].size(); j++) {
      int c = (int) (L[i][j] - 'A');
      t = trie[t][c];
    }
    xl[i] = tl[t];
    xr[i] = tr[t];
  }
  trie.clear();
  trie.emplace_back(vector<int>(26, -1));
  for (int i = 0; i < n; i++) {
    reverse(s[i].begin(), s[i].end());
    int t = 0;
    for (int j = 0; j < (int) s[i].size(); j++) {
      int c = (int) (s[i][j] - 'A');
      if (trie[t][c] == -1) {
        trie[t][c] = trie.size();
        trie.emplace_back(vector<int>(26, -1));
      }
      t = trie[t][c];
    }
  }
  for (int i = 0; i < m; i++) {
    reverse(R[i].begin(), R[i].end());
    int t = 0;
    for (int j = 0; j < (int) R[i].size(); j++) {
      int c = (int) (R[i][j] - 'A');
      if (trie[t][c] == -1) {
        trie[t][c] = trie.size();
        trie.emplace_back(vector<int>(26, -1));
      }
      t = trie[t][c];
    }
  }
  k = trie.size();
  tl.resize(k);
  tr.resize(k);
  T = 0;
  Dfs(0);
  vector<int> y(n);
  vector<int> yl(m), yr(m);
  for (int i = 0; i < n; i++) {
    int t = 0;
    for (int j = 0; j < (int) s[i].size(); j++) {
      int c = (int) (s[i][j] - 'A');
      t = trie[t][c];
    }
    y[i] = tl[t];
  }
  for (int i = 0; i < m; i++) {
    int t = 0;
    for (int j = 0; j < (int) R[i].size(); j++) {
      int c = (int) (R[i][j] - 'A');
      t = trie[t][c];
    }
    yl[i] = tl[t];
    yr[i] = tr[t];
  }
  const int MAX = (int) 2e6 + 5;
  vector<vector<vector<int>>> qs(MAX, vector<vector<int>>(3));
  for (int i = 0; i < n; i++) {
    qs[x[i]][1].push_back(i);
  }
  for (int i = 0; i < m; i++) {
    qs[xl[i]][0].push_back(i);
    qs[xr[i]][2].push_back(i);
  }
  vector<int> ans(m);
  fenwick<int> fenw(MAX);
  for (int i = 0; i < MAX; i++) {
    for (int j : qs[i][0]) {
      ans[j] -= fenw.get(yr[j]) - fenw.get(yl[j] - 1);
    }
    for (int j : qs[i][1]) {
      fenw.modify(y[j], 1);
    }
    for (int j : qs[i][2]) {
      ans[j] += fenw.get(yr[j]) - fenw.get(yl[j] - 1);
    }
  }
  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