Submission #1282810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282810		Jawad_Akbar_JJ	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	221 ms	265128 KiB

selling_rna

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
string en[1<<17], st, s;
int Ans[1<<17], mod = 998244353;
vector<int> hsh[1<<17];

struct node{
	vector<int> vc;
	vector<node*> ch;
	char cur;

	void insert(string &s, int ind, int vl){
		vc.push_back(vl);
		if (ind == s.size())
			return;

		for (int i=0;i<ch.size();i++){
			if (ch[i]->cur == s[ind]){
				ch[i]->insert(s, ind+1, vl);
				return;
			}
		}
		node* Nw = new node();
		Nw->cur = s[ind];
		ch.push_back(Nw);
		Nw->insert(s, ind+1, vl);
	}

	int get(string &s, int ind, int vl){
		if (ind == s.size()){
			int l = -1, r = vc.size();
			while (l + 1 < r){
				int mid = (l + r) / 2;
				if (vc[mid] <= vl)
					r = mid;
				else
					l = mid;
			}
			return vc.size() - r;
		}
		for (int i=0;i<ch.size();i++){
			if (ch[i]->cur == s[ind])
				return ch[i]->get(s, ind+1, vl);
		}
		return 0;
	}
};

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m;
	cin>>n>>m;

	vector<pair<string, int>> vec;
	for (int i=1;i<=n;i++){
		cin>>s;
		vec.push_back({s, i});
	}

	for (int i=1;i<=m;i++){
		cin>>st>>en[i];
		reverse(begin(en[i]), end(en[i]));
		vec.push_back({st, -i});
	}

	sort(begin(vec), end(vec));

	node *rt = new node();
	for (int i=vec.size()-1, id = n;i>=0;i--){
		if (vec[i].second < 0){
			int h = 0;
			s = vec[i].first;
			for (int j=0;j<s.size();j++)
				h = (1LL * h * 256 + s[j]) % mod;
			int l = id, r = n + 1;
			while (l + 1 < r){
				int mid = (l + r) / 2;
				if (hsh[mid].size() >= s.size() and hsh[mid][s.size() - 1] == h)
					l = mid;
				else
					r = mid;
			}

			Ans[-vec[i].second] = rt->get(en[-vec[i].second], 0, l);
		}
		else{
			s = vec[i].first;
			for (int j=0, h = 0;j<s.size();j++)
				h = (1LL * h * 256 + s[j]) % mod, hsh[id].push_back(h);

			reverse(begin(s), end(s));
			rt->insert(s, 0, id);
			id--;
		}
	}

	for (int i=1;i<=m;i++)
		cout<<Ans[i]<<' ';
	cout<<'\n';
}

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