Submission #1289218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289218		misteriousmoth	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	293 ms	555872 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
// ad astra per aspera
#define ll long long
#define ld long double
#define ub upper_bound
#define lb lower_bound
#define check(a, k) ((a) & (1LL << k))
#define fi first
#define se second
#define pll pair<ll, ll>
#define pll_ll pair<pll, ll>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define gcd(x, y) __gcd(x, y)
#define lcm(x, y) ((x / gcd(x, y)) * y)
#define forn(i, n) for (ll i = 0; i < n; i++)
#define rep(i, start, n) for (ll i = start; i <= n; i++)
#define pow2(x) (x) * (x)
const ll M = 1e6 + 5, inf = 1e18 + 5, mod = 1e9 + 7, base[] = {131, 313};
ll n, t, u, v, w, k, m, re = 0, q, ss;

struct Trie
{
	struct node
	{
		node *child[26];
		int exist;
		vector<int> ss;
		node() 
		{
			forn(i, 26) child[i]=NULL;
			exist=0;
		}
	};
	int cur;
	node *root;
	Trie() : cur(0) {root=new node(); }
	void add_string(string s, int i)
	{
		node *p=root;
		for(auto x:s)
		{
			int c=x-'A';
			if(p->child[c]==NULL) p->child[c]=new node();
			p=p->child[c];
			p->ss.push_back(i);
		}
		p->exist++;
	}
	// bool delete_string_recursive(node *p, string& s, int i)
	// {
	// 	if (i != (int)s.size()) {
    //         int c = s[i] - 'a';
    //         bool isChildDeleted = delete_string_recursive(p->child[c], s, i + 1);
    //         if (isChildDeleted) p->child[c] = NULL;
    //     }
    //     else p->exist--;

    //     if (p != root) {
    //         p->cnt--;
    //         if (p->cnt == 0) {
    //             delete(p); 
    //             return true;
    //         }
    //     }
    //     return false;
	// }
	// void delete_string(string s)
	// {
	// 	if(find_string(s)) delete_string_recursive(root, s, 0);
	// }
	int find_string(string s, int l, int r) {
		if(l>r) return 0;
        node* p = root;
        for (auto f : s) {
            int c = f - 'A';
            if (p->child[c] == NULL) return false;
            p = p->child[c];
        }
        return ub(all(p->ss), r)-lb(all(p->ss), l);
    }
	// string find_kth_str(ll k)
	// {
	// 	string re="";
	// 	node *p=root;
	// 	while(1)
	// 	{
	// 		if(p->exist>=k) break;
	// 		k-=p->exist;
	// 		forn(i, 26) if(p->child[i]!=NULL)
	// 		{
	// 			auto nxt = p->child[i];
	// 			if (nxt->cnt >= k) {
	// 				re+=char(i + 'a');
	// 				p=nxt;
	// 				break;
	// 			}
	// 			k -= nxt->cnt;
	// 		}
	// 	}
	// 	return re;
	// }
};
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>t;
	Trie trie;
	vector<string> s(n);
	forn(i, n) cin>>s[i];
	sort(all(s));
	string sp;
	forn(i, n) 
	{
		sp=s[i]; //cout<<sp<<' ';
		reverse(all(sp));
		trie.add_string(sp, i);
	}
	while(t--)
	{
		string pre, suf;
		cin>>pre>>suf;
		reverse(all(suf));
		ll l=lb(all(s), pre)-s.begin(), r=ub(all(s), pre+"[")-s.begin();
		//cout<<l<<' '<<r<<' ';
		cout<<trie.find_string(suf, l, r-1)<<'\n';
	}
	return 0;
}

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