oj.uz

Submission #839477

# Submission time Handle Problem Language Result Execution time Memory
839477 2023-08-30T06:20:27 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 349 ms 205156 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 45 ms 109900 KB Output is correct
2 Correct 45 ms 109836 KB Output is correct
3 Correct 46 ms 109960 KB Output is correct
4 Correct 45 ms 109868 KB Output is correct
5 Correct 46 ms 109840 KB Output is correct
6 Correct 47 ms 109948 KB Output is correct
7 Correct 47 ms 109936 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 205156 KB Output is correct
2 Correct 228 ms 200268 KB Output is correct
3 Correct 164 ms 169600 KB Output is correct
4 Correct 160 ms 167064 KB Output is correct
5 Correct 191 ms 197512 KB Output is correct
6 Correct 192 ms 198756 KB Output is correct
7 Correct 154 ms 120524 KB Output is correct
8 Correct 219 ms 155852 KB Output is correct
9 Correct 211 ms 156412 KB Output is correct
10 Correct 177 ms 155200 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 110692 KB Output is correct
2 Correct 98 ms 110772 KB Output is correct
3 Correct 113 ms 110768 KB Output is correct
4 Correct 104 ms 110548 KB Output is correct
5 Correct 99 ms 110772 KB Output is correct
6 Correct 119 ms 110740 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 109900 KB Output is correct
2 Correct 45 ms 109836 KB Output is correct
3 Correct 46 ms 109960 KB Output is correct
4 Correct 45 ms 109868 KB Output is correct
5 Correct 46 ms 109840 KB Output is correct
6 Correct 47 ms 109948 KB Output is correct
7 Correct 47 ms 109936 KB Output is correct
8 Correct 216 ms 205156 KB Output is correct
9 Correct 228 ms 200268 KB Output is correct
10 Correct 164 ms 169600 KB Output is correct
11 Correct 160 ms 167064 KB Output is correct
12 Correct 191 ms 197512 KB Output is correct
13 Correct 192 ms 198756 KB Output is correct
14 Correct 154 ms 120524 KB Output is correct
15 Correct 219 ms 155852 KB Output is correct
16 Correct 211 ms 156412 KB Output is correct
17 Correct 177 ms 155200 KB Output is correct
18 Correct 124 ms 110692 KB Output is correct
19 Correct 98 ms 110772 KB Output is correct
20 Correct 113 ms 110768 KB Output is correct
21 Correct 104 ms 110548 KB Output is correct
22 Correct 99 ms 110772 KB Output is correct
23 Correct 119 ms 110740 KB Output is correct
24 Correct 251 ms 188620 KB Output is correct
25 Correct 298 ms 188744 KB Output is correct
26 Correct 229 ms 187620 KB Output is correct
27 Correct 187 ms 160440 KB Output is correct
28 Correct 349 ms 131704 KB Output is correct
29 Correct 255 ms 115152 KB Output is correct