oj.uz

Submission #1074712

# Submission time Handle Problem Language Result Execution time Memory
1074712 2024-08-25T13:11:59 Z nima_aryan Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 24 ms 13660 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
vector<char> alpha{'A', 'G', 'C', 'U'};
 
string next(string s) {
  int n = s.size();
  for (int i = n - 1; i >= 0; --i) {
    for (int x = 0; x < 3; ++x) {
      if (s[i] == alpha[x]) {
        s[i] = alpha[x + 1];
        return s;
      }
    }
    s.pop_back();
  }
  return string(n, 'Z');
}
 
constexpr int N = 2.1E5;
vector<array<int, 4>> trie(N);
vector<int> cnt(N);
int tot = 1;
 
void insert(const string& s) {
  int p = 1;
  for (int i = 0; i < s.size(); ++i) {
    int& q = trie[p][find(alpha.begin(), alpha.end(), s[i]) - alpha.begin()];
    if (!q) {
      q = ++tot;
    }
    ++cnt[p = q];
  }
}
int count(const string& s) {
  int p = 1;
  for (int i = 0; i < s.size(); ++i) {
    int q = trie[p][find(alpha.begin(), alpha.end(), s[i]) - alpha.begin()];
    if (!q) {
      return 0;
    }
    p = q;
  }
  return cnt[p];
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  sort(alpha.begin(), alpha.end());
 
  int n, m;
  cin >> n >> m;
 
  vector<string> s(n);
  for (int i = 0; i < n; ++i) {
    cin >> s[i];
  }
 
  sort(s.begin(), s.end());
 
  vector<vector<pair<int, int>>> at(n + 1);
  vector<string> q(m);
  for (int i = 0; i < m; ++i) {
    string p;
    cin >> p >> q[i];
    reverse(q[i].begin(), q[i].end());
    int l = lower_bound(s.begin(), s.end(), p) - s.begin();
    int r = lower_bound(s.begin(), s.end(), next(p)) - s.begin();
    at[l].emplace_back(i, -1);
    at[r].emplace_back(i, +1);
  }
 
  vector<int> ans(m);
  for (int i = 0; i < n; ++i) {
    insert(string(s[i].rbegin(), s[i].rend()));
    for (auto [x, d] : at[i + 1]) {
      ans[x] += d * count(q[x]);
    }
  }
 
  for (int i = 0; i < m; ++i) {
    cout << ans[i] << "\n";
  }
 
  return 0;
}

Compilation message

selling_rna.cpp: In function 'void insert(const string&)':
selling_rna.cpp:28:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for (int i = 0; i < s.size(); ++i) {
      |                   ~~^~~~~~~~~~
selling_rna.cpp: In function 'int count(const string&)':
selling_rna.cpp:38:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for (int i = 0; i < s.size(); ++i) {
      |                   ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 13660 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 10080 KB Output is correct
2 Correct 18 ms 8028 KB Output is correct
3 Correct 23 ms 9688 KB Output is correct
4 Correct 16 ms 8900 KB Output is correct
5 Correct 18 ms 8280 KB Output is correct
6 Correct 23 ms 9564 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4440 KB Output is correct
8 Runtime error 14 ms 13660 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -