Submission #1100159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100159		rayan_bd	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1538 ms	87904 KiB

selling_rna

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

#define all(x) x.begin(),x.end()
#define pb push_back
#define ll long long
const int mxN = 1e5;

unordered_map<char,ll> mp;
vector<ll> emp;

struct Node
{
	vector<ll> end_pos;
	Node* children[4];
	bool end;
	Node(){
		end=0;
		for(ll i=0;i<4;++i) children[i]=NULL;
	}
};

struct Trie{
	Node* root = new Node();
	void add(string str){
		Node* curr = root;
		for(auto it:str){
			if(curr->children[mp[it]]==NULL) curr->children[mp[it]]=new Node();
			curr=curr->children[mp[it]];
		}
		curr->end=1;
	}
	void update_pos(string str,bool from_beg,ll idx){
		Node* curr=root;
		if(!from_beg){
			for(int i=str.size()-1;i>=0;--i){
				char it=str[i];
				if(curr->children[mp[it]]==NULL) return;
				curr=curr->children[mp[it]];
				if(curr->end){
					curr->end_pos.pb(idx);
				}
			}
			return;
		}
		for(auto it:str){
			if(curr->children[mp[it]]==NULL) return;
			curr=curr->children[mp[it]];
			if(curr->end){
				curr->end_pos.pb(idx);
			}
		}
	}
	vector<ll> qry(string str){
		Node* curr = root;
		for(auto it:str){
			curr=curr->children[mp[it]];
		}
		return curr->end_pos;
	}
};

void solve(){
	mp['A']=0;
	mp['C']=1;
	mp['G']=2;
	mp['U']=3;

	Trie pre,suf;
	ll n,m;cin>>n>>m;
	vector<string> vec(n);
	vector<pair<string,string>> pr(m);
	for(ll i=0;i<n;++i){
		cin>>vec[i];
	}
	for(ll i=0;i<m;++i){
		cin>>pr[i].first>>pr[i].second;
		pre.add(pr[i].first);
		reverse(all(pr[i].second));
		suf.add(pr[i].second);
	}
	ll idx=0;
	for(auto it:vec){
		pre.update_pos(it,1,idx);
		suf.update_pos(it,0,idx);
		++idx;
	}
	for(auto it:pr){
		vector<ll> c1=pre.qry(it.first);
		vector<ll> c2=suf.qry(it.second);
		if(c1.size()>c2.size()) swap(c1,c2);
		ll ans=0,nwst=0;
		if(c1.size()==0||c2.size()==0){
			cout<<ans<<'\n';
			continue;
		}
		for(auto it:c1){
			ll st=nwst,en=c2.size()-1;
			while(st<=en){
				ll mid=(st+en)/2;
				if(c2[mid]==it){
					++ans;
					nwst=mid+1;
					break;
				}
				if(c2[mid]>it) en=mid-1;
				else st=mid+1;
			}
		}
		cout<<ans<<'\n';
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	solve();
	return 0;
}

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