Submission #1274254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274254		namhh	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	288 ms	361636 KiB

selling_rna

// e tach VOI huhu
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e6+5;
int n,m,sta[N],ed[N],child[N][4][2],cnt = 0,cnt2 = 0;
string a[N],p[N],q[N];
vector<int>kaori[N];
int val(char x){
	if(x == 'A') return 0;
	if(x == 'G') return 1;
	if(x == 'C') return 2;
	if(x == 'U') return 3;
}
void add(int id, int id1, string s){
	int u = 0;
	for(auto it: s){
		int v = val(it);
		if(!child[u][v][id]){
		    if(id == 0) child[u][v][id] = ++cnt;
		    else child[u][v][id] = ++cnt2;
	    }
		u = child[u][v][id];
		if(id == 1) kaori[u].push_back(id1);
		if(id == 0){
			if(sta[u] == 0) sta[u] = id1;
			ed[u] = id1;
		}
	}
}
int get(int id, string s){
	int u = 0;
	for(auto it: s){
		int v = val(it);
		if(!child[u][v][id]) return 0;
		u = child[u][v][id];
	}
	return u;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1,a+n+1);
	for(int i = 1; i <= n; i++){
		add(0,i,a[i]);
		reverse(a[i].begin(),a[i].end());
		add(1,i,a[i]);
	}
	for(int i = 1; i <= m; i++){
		cin >> p[i] >> q[i];
		int emilia = get(0,p[i]);
		reverse(q[i].begin(),q[i].end());
		int rem = get(1,q[i]);
		int res1 = upper_bound(kaori[rem].begin(),kaori[rem].end(),ed[emilia])-kaori[rem].begin();
		int res2 = lower_bound(kaori[rem].begin(),kaori[rem].end(),sta[emilia])-kaori[rem].begin();
		cout << res1-res2 << "\n";
	}
}

Compilation message (stderr)

selling_rna.cpp: In function 'int val(char)':
selling_rna.cpp:16:1: warning: control reaches end of non-void function [-Wreturn-type]
   16 | }
      | ^

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