Submission #716387

#	Time	Username	Problem	Language	Result	Execution time	Memory
716387		Hyojin	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	190 ms	194208 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define bit(n,i) ((n>>i)&1)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define ep emplace_back
#define pii pair<int,int>
#define piii pair<int,pii>
#define fi first
#define se second
#define ll long long
const int MOD=1e9+7;
const int base=31;
const int N=1e5+5;
int n,q;
string v[N];
int val(char c)
{
	if (c=='A') return 0;
	if (c=='G') return 1;
	if (c=='C') return 2;
	return 3;
}
struct Trie
{
	int l,r;
	Trie *child[4];
	Trie()
	{
		l=1e9,r=-1e9;
		memset(child,0,sizeof child);
	}
};
Trie root;
void trieAdd(const string &s,int pos)
{
	Trie *p=&root;
	int n=s.size();
	for (int i=0;i<n;i++)
	{
		int c=val(s[i]);
		if (!p->child[c]) p->child[c]=new Trie();
		p=p->child[c];
		p->l=min(p->l,pos);
		p->r=max(p->r,pos);
	}
}
pair<int,int>getRange(const string &s)
{
	Trie *p=&root;
	int n=s.size();
	for (int i=0;i<n;i++)
	{
		int c=val(s[i]);
		if (!p->child[c]) return {0,0};
		p=p->child[c];
	}
	return {p->l,p->r};
}
struct revTrie
{
	revTrie *child[4];
	vector<int>vi;
	revTrie()
	{
		vi.clear();
		memset(child,0,sizeof child);
	}
};
revTrie r;
void revAdd(const string &s,int pos)
{
	revTrie *p=&r;
	int n=s.size();
	for (int i=n-1;~i;i--)
	{
		int c=val(s[i]);
		if (!p->child[c]) p->child[c]=new revTrie();
		p=p->child[c];
		p->vi.pb(pos);
	}
}
int revFind(const string &s,pair<int,int>range)
{
	revTrie *p=&r;
	int n=s.size();
	for (int i=n-1;~i;i--)
	{
		int c=val(s[i]);
		p=p->child[c];
	}
	int it1=lower_bound(all(p->vi),range.fi)-(p->vi.begin());
	int it2=upper_bound(all(p->vi),range.se)-(p->vi.begin());
	return it2-it1;
}
int main()
{
	#ifdef Hyojin
    	freopen("input.txt", "r", stdin);
    	freopen("output.txt", "w", stdout);
	#endif //Hyojin
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for (int i=1;i<=n;i++)
	{
		cin>>v[i];
	}
	sort(v+1,v+n+1);
	for (int i=1;i<=n;i++)
	{
		trieAdd(v[i],i);
	}
	for (int i=1;i<=n;i++)
	{
		revAdd(v[i],i);
	}
	while (q--)
	{
		string p,q;
		cin>>p>>q;
		pair<int,int>x=getRange(p);
		if (x.se==0) cout<<0;
		else
		{
			int ans=revFind(q,x);
			cout<<ans;
		}
		cout<<"\n";
	}
	return 0;
}

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