Submission #552149

#	Time	Username	Problem	Language	Result	Execution time	Memory
552149		nishkarsh	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	446 ms	223516 KiB

selling_rna

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
using namespace std;
ll powmod(ll base,ll exponent,ll mod){
	ll ans=1;
	if(base<0) base+=mod;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
const int INF = 2e9;
const ll INFLL = 4e18;
const int upperlimit = 1e6+1;
const int mod = 1e9+7;
const int letters = 4;
string inp[upperlimit];
int toint(char c){
	if(c=='A') return 0;
	if(c=='U') return 1;
	if(c=='G') return 2;
	return 3;
}
struct trie_node
{
	vi indices;
	int child[letters];
	trie_node(){
		for(int i = 0; i < letters; i++) child[i]=0;
	}
};
trie_node default_trienode;
class trie {
	vector<trie_node> tree;
	int cur_node,sz=1;
public:
	trie() {
		tree.resize(1);
	}
	void addstring(string s,int ind){
		cur_node=0;
		for(auto i : s){
			tree[cur_node].indices.pb(ind);
			if(! tree[cur_node].child[toint(i)]){
				tree[cur_node].child[toint(i)]=sz++;
				tree.pb(default_trienode);
			}
			cur_node = tree[cur_node].child[toint(i)];
		}
		tree[cur_node].indices.pb(ind);
	}
	pii query_range(string s){
		cur_node = 0;
		for(auto i : s){
			if(! tree[cur_node].child[toint(i)]) return(mp(0,0));
			cur_node = tree[cur_node].child[toint(i)];
		}
		return mp(tree[cur_node].indices.front(),tree[cur_node].indices.back());
	}
	int query(string s,int l,int r){
		cur_node = 0;
		for(auto i : s){
			if(! tree[cur_node].child[toint(i)]) return 0;
			cur_node = tree[cur_node].child[toint(i)];
		}
		return int(upper_bound(tree[cur_node].indices.begin(),tree[cur_node].indices.end(),r) - lower_bound(tree[cur_node].indices.begin(),tree[cur_node].indices.end(),l));
	}
};
int main(){
	int n,m;
	string pref,suff;
	trie str,revstr;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> inp[i];
	sort(inp+1,inp+n+1);
	for(int i = 1; i <= n; i++){
		str.addstring(inp[i],i);
		reverse(inp[i].begin(),inp[i].end());
		revstr.addstring(inp[i],i);
	}
	while(m--){
		cin >> pref >> suff;
		pii range = str.query_range(pref);
		reverse(suff.begin(),suff.end());
		cout << revstr.query(suff,range.F,range.S) << "\n";
	}
	return 0;
}

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