oj.uz

Submission #516698

# Submission time Handle Problem Language Result Execution time Memory
516698 2022-01-21T22:05:56 Z MilosMilutinovic Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 732 ms 493112 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 211700 KB Output is correct
2 Correct 163 ms 211680 KB Output is correct
3 Correct 172 ms 211668 KB Output is correct
4 Correct 159 ms 211628 KB Output is correct
5 Correct 164 ms 211748 KB Output is correct
6 Correct 159 ms 211612 KB Output is correct
7 Correct 156 ms 211684 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 493112 KB Output is correct
2 Correct 598 ms 478356 KB Output is correct
3 Correct 506 ms 285576 KB Output is correct
4 Correct 505 ms 275440 KB Output is correct
5 Correct 732 ms 386760 KB Output is correct
6 Correct 732 ms 389336 KB Output is correct
7 Correct 266 ms 218476 KB Output is correct
8 Correct 653 ms 319280 KB Output is correct
9 Correct 594 ms 303792 KB Output is correct
10 Correct 492 ms 297424 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 218692 KB Output is correct
2 Correct 203 ms 216960 KB Output is correct
3 Correct 207 ms 218296 KB Output is correct
4 Correct 179 ms 216748 KB Output is correct
5 Correct 205 ms 216560 KB Output is correct
6 Correct 205 ms 217876 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 211700 KB Output is correct
2 Correct 163 ms 211680 KB Output is correct
3 Correct 172 ms 211668 KB Output is correct
4 Correct 159 ms 211628 KB Output is correct
5 Correct 164 ms 211748 KB Output is correct
6 Correct 159 ms 211612 KB Output is correct
7 Correct 156 ms 211684 KB Output is correct
8 Correct 572 ms 493112 KB Output is correct
9 Correct 598 ms 478356 KB Output is correct
10 Correct 506 ms 285576 KB Output is correct
11 Correct 505 ms 275440 KB Output is correct
12 Correct 732 ms 386760 KB Output is correct
13 Correct 732 ms 389336 KB Output is correct
14 Correct 266 ms 218476 KB Output is correct
15 Correct 653 ms 319280 KB Output is correct
16 Correct 594 ms 303792 KB Output is correct
17 Correct 492 ms 297424 KB Output is correct
18 Correct 178 ms 218692 KB Output is correct
19 Correct 203 ms 216960 KB Output is correct
20 Correct 207 ms 218296 KB Output is correct
21 Correct 179 ms 216748 KB Output is correct
22 Correct 205 ms 216560 KB Output is correct
23 Correct 205 ms 217876 KB Output is correct
24 Correct 513 ms 447908 KB Output is correct
25 Correct 527 ms 451328 KB Output is correct
26 Correct 510 ms 444160 KB Output is correct
27 Correct 471 ms 272980 KB Output is correct
28 Correct 351 ms 264640 KB Output is correct
29 Correct 218 ms 229060 KB Output is correct