Submission #1267949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267949		duyanhchupapi	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	168 ms	221040 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std; using ll = long long; const int N = 100005;
int I[300], inf = 1e9;
struct pre {
	pre* child[4]; int MAX, MIN;
	pre() { for(int i=0;i<4;++i) child[i] = nullptr ; MIN = inf; MAX = 0;}
} root;

struct suf {
	suf* child[4]; vector<int> ID; bool ok;
	suf() {for(int i=0;i<4;++i) child[i] = nullptr; ok = 0; } 
} ROOT;

void add(string s, int id) {
	pre* p = &root;
	for(char c : s) {
		if(p->child[I[c]] == nullptr) p->child[I[c]] = new pre();
		p = p->child[I[c]];
		p->MIN = min(p->MIN, id);
		p->MAX = max(p->MAX, id);
	}
	suf* P = &ROOT;
	for(int i=s.length()-1;i>=0;--i) {
		if(P->child[I[s[i]]] == nullptr) P->child[I[s[i]]] = new suf();
		P = P->child[I[s[i]]];
		P->ID.push_back(id);
	}
}

pair<int,int> query(string s) {
	pre* p = &root;
	for(char c : s) {
		if(p->child[I[c]] == nullptr) return make_pair(inf,inf);
		p = p->child[I[c]];
	}	
	return make_pair(p->MIN, p->MAX);
}

int get(string s, int L, int R) {
	reverse(s.begin(), s.end());
	suf* P = &ROOT;
	for(char c : s) {
		if(P->child[I[c]] == nullptr) return 0;
		P = P->child[I[c]];
	}
	if(!P->ok) sort(P->ID.begin(), P->ID.end()), P->ok = 1;	
	int res = upper_bound(P->ID.begin(), P->ID.end(), R) - lower_bound(P->ID.begin(), P->ID.end(), L);
	return max(res, 0);
}
string s[N];
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	I['A'] = 0;
	I['U'] = 1;
	I['G'] = 2;
	I['C'] = 3;
	int n, m; 
	cin >> n >> m;
	for(int i=1;i<=n;++i) cin >> s[i];
	sort(s+1,s+n+1);
	for(int i=1;i<=n;++i) add(s[i], i);
	while(m--) {
		string p, q;
		cin >> p >> q;
		pair<int,int> lim = query(p);
		cout << get(q, lim.first, lim.second) << '\n';
	}
	return 0;
}

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