Submission #1235539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235539		nai0610	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	144 ms	144976 KiB

selling_rna

#include <bits/stdc++.h>
#define ll int64_t
#define ld long double
using namespace std;
// 
const int maxn =1e5+5;
const int maxm =2e6+5;
const int mod = 1e9+7; // 998244353,1610612741
const ll inf = 1e18;
const ld pi = atan(1.0L)*4;
int n,Q,m[420];
int t[2][maxm][4],it[2],L[maxm],R[maxm];
string a[maxn];
vector<int> pos[maxm];
void add(int id,const string& s,int i,bool rev){
	int u=1;
	for (int j=0;j<s.size();j++) {
		int c=m[(rev?s[s.size()-1-j]:s[j])];
		if (!t[id][u][c]) t[id][u][c]=++it[id];
		u=t[id][u][c];
		if (id==0) {
			if (!L[u]) L[u]=i;
			R[u]=i;
		}
		else pos[u].push_back(i);
	}
}
int get(int id,const string& s,bool rev) {
	int u=1;
	for (int j=0;j<s.size();j++) {
		int c=m[(rev?s[s.size()-1-j]:s[j])];
		u=t[id][u][c];
		if (!u) return 0;
	}
	return u;
}
int main() {
    // freopen("../input.inp","r",stdin);
    // freopen("output.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    clock_t start,end;
	start=clock();
	m['A']=0;
	m['G']=1;
	m['C']=2;
	m['U']=3;
	cin >>n>>Q;
	it[0]=it[1]=1;
	for (int i=1;i<=n;i++) cin >>a[i];
	sort(a+1,a+1+n);
	for (int i=1;i<=n;i++) {
		add(0,a[i],i,0);
		add(1,a[i],i,1);
	}
	while (Q--) {
		string p,q;
		cin >>p>>q;
		int u=get(0,p,0),v=get(1,q,1);
		cout <<max(0,(int)(upper_bound(pos[v].begin(),pos[v].end(),R[u])-
					 lower_bound(pos[v].begin(),pos[v].end(),L[u])))<<'\n';
	}
	end=clock();
	ld dur=(ld)(end-start)/(ld)(CLOCKS_PER_SEC)*(1000.0L);
	cerr<<dur<<'\n';
    return 0;
}

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