Submission #1258816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258816		arashmemar	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	458 ms	558176 KiB

selling_rna

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

const int maxn = 1e5 + 100, mod = 1e9 + 7, p = 701;

long long int ptp[maxn];
vector <int> h[maxn];
string s[maxn];
int cnt;

void init(string s, int ind)
{
	h[ind].push_back(0);
	for (int i = 0;i < s.size();i++)
	{
		h[ind].push_back((h[ind][i] + ptp[i] * s[i] % mod) % mod);
	}
	return ;
}

bool cmp(int a, int b)
{
	int l = 0, r = min(h[a].size(), h[b].size());
	while (r - l - 1)
	{
		int mid = (l + r) / 2;
		if (h[a][mid] == h[b][mid])
		{
			l = mid;
		}
		else
		{
			r = mid;
		}
	}
	if (r == min(h[a].size(), h[b].size()))
	{
		return h[a].size() < h[b].size();
	}
	return s[a][l] < s[b][l];
}

int a[maxn];

struct Node
{
	int L, R, mid;
	vector <int> s;
	Node *lc, *rc;

	Node (int l, int r)
	{
		L = l, R = r, mid = (L + R) / 2, lc = rc = NULL;
		return ;
	}

	void init()
	{
		if (R - L == 1)
		{
			s.push_back(a[L]);
			return ;
		}
		lc = new Node(L, mid);
		rc = new Node(mid, R);
		lc->init();
		rc->init();
		int lptr = 0, rptr = 0;
		while (lptr != mid - L or rptr != R - mid)
		{
			if (rptr == R - mid or (lptr != mid - L and lc->s[lptr] < rc->s[rptr]))
			{
				s.push_back(lc->s[lptr]);
				lptr++;
			}
			else
			{
				s.push_back(rc->s[rptr]);
				rptr++;
			}
		}
		return ;
	}

	int get(int l, int r, int x, int y)
	{
		if (l >= r or l < L or r > R or x > y)
		{
			return 0;
		}
		if (l == L and R == r)
		{
			return upper_bound(s.begin(), s.end(), y) - lower_bound(s.begin(), s.end(), x);
		}
		int ret = 0;
		if (l < mid)
		{
			ret += lc->get(l, min(r, mid), x, y);
		}
		if (r > mid)
		{
			ret += rc->get(max(l, mid), r, x, y);
		}
		return ret;
	}
};

struct T
{
	int L, R, st, ft;
	vector <int> add;
	T* ch[21];

	T()
	{
		L = maxn, R = 0, st = ft = 0;
		for (int i = 0;i < 21;i++)
		{
			ch[i] = NULL;
		}
		return ;
	}

	void insert(int ptr, int ind, int w)
	{
		L = min(L, w);
		R = max(R, w);
		if (ptr == s[ind].size())
		{
			add.push_back(w);
			return ;
		}
		int g = s[ind][ptr] - 'A';
		if (ch[g] == NULL)
		{
			ch[g] = new T();
		}
		ch[g]->insert(ptr + 1, ind, w);
		return ;
	}

	pair <int, int> get(int ptr)
	{
		if (ptr == s[0].size())
		{
			return {L, R};
		}
		int g = s[0][ptr] - 'A';
		if (ch[g] == NULL)
		{
			return {maxn, 0};
		}
		return ch[g]->get(ptr + 1);
	}

	void dfs()
	{
		st = cnt + 1;
		for (auto o : add)
		{
			a[++cnt] = o;
		}
		for (int g = 0;g < 21;g++)
		{
			if (ch[g])
			{
				ch[g]->dfs();
			}
		}
		ft = cnt + 1;
		return ;
	}

	pair <int, int> getsf(int ptr, int ind)
	{
		if (ptr == s[ind].size())
		{
			return {st, ft};
		}
		int g = s[ind][ptr] - 'A';
		if (ch[g])
		{
			return ch[g]->getsf(ptr + 1, ind);
		}
		return {0, 0};
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	T *pre, *suf;
	pre = new T();
	suf = new T();
	ptp[0] = 1;
	for (int i = 1;i < maxn;i++)
	{
		ptp[i] = ptp[i - 1] * p % mod;
	}
	int n, m;
	cin >> n >> m;
	vector <int> tmp;
	for (int i = 1;i <= n;i++)
	{
		cin >> s[i];
		init(s[i], i);
		tmp.push_back(i);
	}
	sort(tmp.begin(), tmp.end(), cmp);
	int it = 0;
	for (auto o : tmp)
	{
		pre->insert(0, o, ++it);
		reverse(s[o].begin(), s[o].end());
		suf->insert(0, o, it);
		reverse(s[o].begin(), s[o].end());
	}
	suf->dfs();
	Node* root = new Node(1, cnt + 1);
	root->init();

	for (int i = 1;i <= cnt;i++)
	{
//		cout << a[i] << ' ';
	}
	//cout << endl;

	while (m--)
	{
		cin >> s[0];
		pair <int, int> tmp1 = pre->get(0);
		cin >> s[0];
		reverse(s[0].begin(), s[0].end());
		pair <int, int> tmp2 = suf->getsf(0, 0);
		//cout << tmp1.first << ' ' << tmp1.second << endl;
		//cout << tmp2.first << ' ' << tmp2.second << endl;
		cout << root->get(tmp2.first, tmp2.second, tmp1.first, tmp1.second) << '\n';
	}
}

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