oj.uz

Submission #516697

# Submission time Handle Problem Language Result Execution time Memory
516697 2022-01-21T21:53:12 Z MilosMilutinovic Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 285584 KB 
#include <bits/stdc++.h>

using namespace std;

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];
  }
  for (int i = 0; i < m; i++) {
    int ans = 0;
    for (int j = 0; j < n; j++) {
      if (xl[i] <= x[j] && x[j] <= xr[i] && yl[i] <= y[j] && y[j] <= yr[i]) {
        ans += 1;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 285584 KB Output is correct
2 Correct 553 ms 270780 KB Output is correct
3 Correct 505 ms 281656 KB Output is correct
4 Correct 532 ms 268360 KB Output is correct
5 Correct 623 ms 186844 KB Output is correct
6 Correct 635 ms 189568 KB Output is correct
7 Correct 98 ms 12208 KB Output is correct
8 Correct 548 ms 113712 KB Output is correct
9 Correct 494 ms 102560 KB Output is correct
10 Correct 327 ms 90596 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1548 ms 6660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 403 ms 285584 KB Output is correct
9 Correct 553 ms 270780 KB Output is correct
10 Correct 505 ms 281656 KB Output is correct
11 Correct 532 ms 268360 KB Output is correct
12 Correct 623 ms 186844 KB Output is correct
13 Correct 635 ms 189568 KB Output is correct
14 Correct 98 ms 12208 KB Output is correct
15 Correct 548 ms 113712 KB Output is correct
16 Correct 494 ms 102560 KB Output is correct
17 Correct 327 ms 90596 KB Output is correct
18 Execution timed out 1548 ms 6660 KB Time limit exceeded
19 Halted 0 ms 0 KB -