oj.uz

Submission #1074703

# Submission time Handle Problem Language Result Execution time Memory
1074703 2024-08-25T13:04:08 Z nima_aryan Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 182 ms 254032 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 = 1.2E7;
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 88 ms 235088 KB Output is correct
2 Correct 96 ms 235092 KB Output is correct
3 Correct 98 ms 235088 KB Output is correct
4 Correct 82 ms 235092 KB Output is correct
5 Correct 91 ms 235144 KB Output is correct
6 Correct 88 ms 235092 KB Output is correct
7 Correct 109 ms 235248 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 241592 KB Output is correct
2 Correct 119 ms 242016 KB Output is correct
3 Correct 135 ms 243824 KB Output is correct
4 Correct 127 ms 243792 KB Output is correct
5 Correct 112 ms 240208 KB Output is correct
6 Correct 118 ms 240216 KB Output is correct
7 Correct 125 ms 244580 KB Output is correct
8 Correct 133 ms 245796 KB Output is correct
9 Correct 121 ms 245808 KB Output is correct
10 Correct 122 ms 242060 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 241240 KB Output is correct
2 Correct 101 ms 239184 KB Output is correct
3 Correct 108 ms 240280 KB Output is correct
4 Correct 100 ms 239436 KB Output is correct
5 Correct 112 ms 239160 KB Output is correct
6 Correct 111 ms 240184 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 235088 KB Output is correct
2 Correct 96 ms 235092 KB Output is correct
3 Correct 98 ms 235088 KB Output is correct
4 Correct 82 ms 235092 KB Output is correct
5 Correct 91 ms 235144 KB Output is correct
6 Correct 88 ms 235092 KB Output is correct
7 Correct 109 ms 235248 KB Output is correct
8 Correct 104 ms 241592 KB Output is correct
9 Correct 119 ms 242016 KB Output is correct
10 Correct 135 ms 243824 KB Output is correct
11 Correct 127 ms 243792 KB Output is correct
12 Correct 112 ms 240208 KB Output is correct
13 Correct 118 ms 240216 KB Output is correct
14 Correct 125 ms 244580 KB Output is correct
15 Correct 133 ms 245796 KB Output is correct
16 Correct 121 ms 245808 KB Output is correct
17 Correct 122 ms 242060 KB Output is correct
18 Correct 110 ms 241240 KB Output is correct
19 Correct 101 ms 239184 KB Output is correct
20 Correct 108 ms 240280 KB Output is correct
21 Correct 100 ms 239436 KB Output is correct
22 Correct 112 ms 239160 KB Output is correct
23 Correct 111 ms 240184 KB Output is correct
24 Correct 124 ms 243288 KB Output is correct
25 Correct 131 ms 245448 KB Output is correct
26 Correct 113 ms 242464 KB Output is correct
27 Correct 124 ms 245296 KB Output is correct
28 Correct 174 ms 254032 KB Output is correct
29 Correct 182 ms 249944 KB Output is correct