oj.uz

Submission #882995

# Submission time Handle Problem Language Result Execution time Memory
882995 2023-12-04T11:30:39 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 353 ms 210364 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> vv[2000005];
int t[2][4][2000005], a[2000005], b[2000005], n, m, d[2];
string s[2000005];
int check(char c) {
    if (c == 'A') return 0;
    if (c == 'C') return 1;
    if (c == 'G') return 2;
    return 3;
}
void add(string s, int j, int h, int flag) {
	int k = 1;
	for (int i = 0; i < s.size(); i++) {
	    int c;
        if (flag == 1) c = check(s[s.size() - i - 1]);
        else c = check(s[i]);
		if (t[h][c][k] == 0) t[h][c][k] = d[h]++;
		k = t[h][c][k];
		if (h == 0) {
			if (a[k] == 0) a[k] = j;
			b[k] = max(b[k], j);
		}
		else vv[k].push_back(j);
	}
}
int get(string s, int h, int flag) {
	int k = 1;
	for (int i = 0; i < s.size(); i++) {
	    int c;
        if (flag == 1) c = check(s[s.size() - i - 1]);
        else c = check(s[i]);
		k = t[h][c][k];
		if (k == 0) return 0;
	}
	return k;
}
int main() {
	cin >> n >> m;
	d[0] = d[1] = 2;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
    }
    sort(s, s + n);
	for (int i = 0; i < n; i++) {
		add(s[i], i + 1, 0, 0);
		add(s[i], i + 1, 1, 1);
	}
	for (int i = 0; i < m; i++) {
		string s, t;
		cin >> s >> t;
		int h = get(s, 0, 0), k = get(t, 1, 1);
		int g = lower_bound(vv[k].begin(), vv[k].end(), a[h]) - vv[k].begin(), l = upper_bound(vv[k].begin(), vv[k].end(), b[h]) - vv[k].begin();
		cout << max(0, l - g) << '\n';
	}
}

Compilation message

selling_rna.cpp: In function 'void add(std::string, int, int, int)':
selling_rna.cpp:16:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for (int i = 0; i < s.size(); i++) {
      |                  ~~^~~~~~~~~~
selling_rna.cpp: In function 'int get(std::string, int, int)':
selling_rna.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (int i = 0; i < s.size(); i++) {
      |                  ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 112332 KB Output is correct
2 Correct 24 ms 112220 KB Output is correct
3 Correct 24 ms 112220 KB Output is correct
4 Correct 25 ms 112220 KB Output is correct
5 Correct 28 ms 112220 KB Output is correct
6 Correct 24 ms 112220 KB Output is correct
7 Correct 24 ms 112220 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 210364 KB Output is correct
2 Correct 210 ms 206160 KB Output is correct
3 Correct 155 ms 174632 KB Output is correct
4 Correct 140 ms 172404 KB Output is correct
5 Correct 171 ms 201300 KB Output is correct
6 Correct 185 ms 202576 KB Output is correct
7 Correct 131 ms 128304 KB Output is correct
8 Correct 226 ms 162828 KB Output is correct
9 Correct 196 ms 163408 KB Output is correct
10 Correct 147 ms 159848 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 113784 KB Output is correct
2 Correct 86 ms 113596 KB Output is correct
3 Correct 94 ms 113492 KB Output is correct
4 Correct 81 ms 113504 KB Output is correct
5 Correct 78 ms 113568 KB Output is correct
6 Correct 108 ms 113632 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 112332 KB Output is correct
2 Correct 24 ms 112220 KB Output is correct
3 Correct 24 ms 112220 KB Output is correct
4 Correct 25 ms 112220 KB Output is correct
5 Correct 28 ms 112220 KB Output is correct
6 Correct 24 ms 112220 KB Output is correct
7 Correct 24 ms 112220 KB Output is correct
8 Correct 200 ms 210364 KB Output is correct
9 Correct 210 ms 206160 KB Output is correct
10 Correct 155 ms 174632 KB Output is correct
11 Correct 140 ms 172404 KB Output is correct
12 Correct 171 ms 201300 KB Output is correct
13 Correct 185 ms 202576 KB Output is correct
14 Correct 131 ms 128304 KB Output is correct
15 Correct 226 ms 162828 KB Output is correct
16 Correct 196 ms 163408 KB Output is correct
17 Correct 147 ms 159848 KB Output is correct
18 Correct 108 ms 113784 KB Output is correct
19 Correct 86 ms 113596 KB Output is correct
20 Correct 94 ms 113492 KB Output is correct
21 Correct 81 ms 113504 KB Output is correct
22 Correct 78 ms 113568 KB Output is correct
23 Correct 108 ms 113632 KB Output is correct
24 Correct 235 ms 194908 KB Output is correct
25 Correct 280 ms 195172 KB Output is correct
26 Correct 214 ms 194184 KB Output is correct
27 Correct 171 ms 165716 KB Output is correct
28 Correct 353 ms 138468 KB Output is correct
29 Correct 252 ms 120776 KB Output is correct