Submission #398827

#	Time	Username	Problem	Language	Result	Execution time	Memory
398827		nikatamliani	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	402 ms	398676 KiB

selling_rna

#include "bits/stdc++.h"
using namespace std;
const int N = 2e5+10;
string s[N];
int n, m;
int count(const vector<int> &v, int x) {
	if(v.empty()) return 0;
	int l = 0, r = (int)v.size()-1, pos = -1;
	while(r >= l) {
		int m = l + r >> 1;
		if(v[m] <= x) {
			pos = m;
			l = m + 1;
		} else {
			r = m - 1;
		}
	}
	return pos+1;
}
int count(const vector<int> &v, int L, int R) {
	return count(v, R) - count(v, L-1);
}
int id[256];
struct trie {
	int tries;
	vector<array<int, 4>> nxt;
	vector<vector<int>> ids;
	trie() {}
	trie(int size) {
		tries = 0;
		nxt = vector<array<int, 4>>(size);
		ids = vector<vector<int>>(size);
	}
	void add(const string &s, int pos) {
		int cur = 0;
		for(int i = 0; i < (int)s.size(); ++i) {
			if(nxt[cur][id[s[i]]] == 0) {
				nxt[cur][id[s[i]]] = ++tries;
			}
			cur = nxt[cur][id[s[i]]];
			ids[cur].push_back(pos);
	 	}
	}
	int get(const string &s, int L, int R) {
		int cur = 0;
		for(int i = 0; i < (int)s.size(); ++i) {
			cur = nxt[cur][id[s[i]]];
		}
		return count(ids[cur], L, R);
	}
	pair<int, int> get(const string &s) {
		int cur = 0;
		for(int i = 0; i < (int)s.size(); ++i) {
			cur = nxt[cur][id[s[i]]];
		}
		if(ids[cur].empty()) {
			return {0, 0};
		}
		return {ids[cur][0], ids[cur].back()};
	}
};
int main() {
	id['A'] = 1;
	id['U'] = 2;
	id['G'] = 3;
	id['C'] = 4;
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		cin >> s[i];
	}
	sort(s+1, s+n+1);
	trie t1(20*N), t2(20*N);
	for(int i = 1; i <= n; ++i) {
		t1.add(s[i], i);
		reverse(s[i].begin(), s[i].end());
		t2.add(s[i], i);
		reverse(s[i].begin(), s[i].end());
	}
	for(int i = 1; i <= m; ++i) {
		string p, q; cin >> p >> q;
		reverse(q.begin(), q.end());
		pair<int, int> LR = t1.get(p);
		cout << t2.get(q, LR.first, LR.second) << '\n';
	}
}

Compilation message (stderr)

selling_rna.cpp: In function 'int count(const std::vector<int>&, int)':
selling_rna.cpp:10:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 |   int m = l + r >> 1;
      |           ~~^~~
selling_rna.cpp: In member function 'void trie::add(const string&, int)':
selling_rna.cpp:37:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   37 |    if(nxt[cur][id[s[i]]] == 0) {
      |                       ^
selling_rna.cpp:38:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   38 |     nxt[cur][id[s[i]]] = ++tries;
      |                     ^
selling_rna.cpp:40:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   40 |    cur = nxt[cur][id[s[i]]];
      |                          ^
selling_rna.cpp: In member function 'int trie::get(const string&, int, int)':
selling_rna.cpp:47:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   47 |    cur = nxt[cur][id[s[i]]];
      |                          ^
selling_rna.cpp: In member function 'std::pair<int, int> trie::get(const string&)':
selling_rna.cpp:54:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   54 |    cur = nxt[cur][id[s[i]]];
      |                          ^

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40