Submission #245905

#	Time	Username	Problem	Language	Result	Execution time	Memory
245905		Goolakh	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	133 ms	46456 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Os")

#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=1e5+10, maxm=1e3+10, lg=21, mod=1e9+7, inf=1e18;

ll n,q,C[maxn][4],nn,tt,wat[maxn],st[maxn],ft[maxn],cnt[maxn],ans[maxn];
vector<ll> qq[maxn];
vector<pll> Q[maxn];
string s[maxn],pre[maxn],suf[maxn];

ll add(string s){
	ll v=0;
	for(auto c:s) cnt[v=C[v][c-'a']=(!C[v][c-'a'] ? ++nn:C[v][c-'a'])]++;
	return v;
}
ll dff(string s){
	ll v=0;
	for(auto c:s){
		v=C[v][c-'a'];
		if(v==0) break;
	}
	return v;
}
void dfs(ll v=0){
	wat[st[v]=tt++]=v;
	for(int i:{0,1,2,3})if(C[v][i]) dfs(C[v][i]);
	ft[v]=tt;
}
map<char,char> num;
void mkay(string &s){for(auto &c:s) c=num[c];}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	num['A']='a', num['C']='b', num['G']='c', num['U']='d';
	cin>>n>>q;
	for(int i=0;i<n;i++){
		cin>>s[i]; mkay(s[i]);
		qq[add(s[i])].pb(i);
		reverse(all(s[i]));
	}
	dfs();
	for(int i=0;i<q;i++){
		cin>>pre[i]>>suf[i]; mkay(pre[i]), mkay(suf[i]);
		ll v=dff(pre[i]);
		if(v){
			Q[st[v]].pb({-1,i});
			Q[ft[v]].pb({+1,i});
			reverse(all(suf[i]));
		}
	}
	memset(C,0,sizeof(C)), memset(cnt,0,sizeof(cnt)), nn=0;
	for(int i=0;i<=tt;i++){
		for(auto x:Q[i]){
			ll v=dff(suf[x.S]);
			if(v) ans[x.S]+=x.F*cnt[v];
		}
		for(auto x:qq[wat[i]]) add(s[x]);
	}
	for(int i=0;i<q;i++) cout<<ans[i]<<endl;
 	
	return 0;
}

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