Submission #839476

#	Time	Username	Problem	Language	Result	Execution time	Memory
839476		adaawf	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	385 ms	205236 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40