Submission #366699

#	Time	Username	Problem	Language	Result	Execution time	Memory
366699		Rainbowbunny	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	910 ms	614988 KiB

selling_rna

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <chrono>
#include <random>
#include <bitset>
#include <utility>

int convert(char x)
{
	if(x == 'A')
	{
		return 0;
	}
	else if(x == 'G')
	{
		return 1;
	}
	else if(x == 'C')
	{
		return 2;
	}
	else if(x == 'U')
	{
		return 3;
	}
	assert(false);
}

struct node
{
	int nxt[4];
	int cnt;
	node()
	{
		for(int i = 0; i < 4; i++)
		{
			nxt[i] = -1;
		}	
		cnt = 0;
	}
};

struct Trie
{
	std::vector <node> Tree;
	Trie()
	{
		Tree.resize(1);	
	}	
	void Add(std::string &s)
	{
		int node = 0;
		Tree[node].cnt++;
		for(auto x : s)
		{
			int tmp = convert(x);
			if(Tree[node].nxt[tmp] == -1)
			{
				Tree[node].nxt[tmp] = (int)Tree.size();
				Tree.emplace_back();
			}
			node = Tree[node].nxt[tmp];
			Tree[node].cnt++;
		}
	}
	int Count(std::string &s)
	{
		int node = 0;
		for(auto x : s)
		{
			int tmp = convert(x);
			if(Tree[node].nxt[tmp] == -1)
			{
				return 0;
			}
			node = Tree[node].nxt[tmp];
		}
		return Tree[node].cnt;
	}
};

int timer;
std::vector <int> tin, tout;
std::vector <std::pair <int, int> > Position;
Trie Prefix;
Trie IT[1 << 19 | 5];

int n;
std::string s[100005];

int q;

void DFS(int node)
{
	timer++;
	tin[node] = timer;
	for(int i = 0; i < 4; i++)
	{
		if(Prefix.Tree[node].nxt[i] != -1)
		{
			DFS(Prefix.Tree[node].nxt[i]);
		}
	}
	tout[node] = timer;
}

void Cal()
{
	tin.resize(Prefix.Tree.size());
	tout.resize(Prefix.Tree.size());
	DFS(0);	
	for(int i = 0; i < n; i++)
	{
		int node = 0;
		for(auto x : s[i])
		{
			node = Prefix.Tree[node].nxt[convert(x)];
		}
		Position.emplace_back(tin[node], i);
	}
	std::sort(Position.begin(), Position.end());
}

void Build(int node, int l, int r)
{
	
	for(int i = l; i <= r; i++)
	{
		IT[node].Add(s[Position[i].second]);
	}
	if(l != r)
	{
		int mid = (l + r) >> 1;
		Build(node << 1, l, mid);
		Build(node << 1 | 1, mid + 1, r);
	}
}

int Get(int node, int l, int r, int L, int R, std::string &s)
{
	if(L > r or R < l)
	{
		return 0;
	}
	if(L <= l and r <= R)
	{
		return IT[node].Count(s);
	}
	int mid = (l + r) >> 1;
	return Get(node << 1, l, mid, L, R, s) + Get(node << 1 | 1, mid + 1, r, L, R, s);
}

void BuildMergeSortTree()
{
	for(int i = 0; i < n; i++)
	{
		reverse(s[i].begin(), s[i].end());
	}
	Build(1, 0, n - 1);
}

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> n >> q;
	for(int i = 0; i < n; i++)
	{
		std::cin >> s[i];
		Prefix.Add(s[i]);
	}
	Cal();
	BuildMergeSortTree();
	while(q--)
	{
		std::string pre, suf;
		std::cin >> pre >> suf;
		reverse(suf.begin(), suf.end());
		int node = 0;
		for(auto x : pre)
		{
			int tmp = convert(x);
			if(Prefix.Tree[node].nxt[tmp] == -1)
			{
				node = -1;
				break;
			}
			node = Prefix.Tree[node].nxt[tmp];
		}
		if(node == -1)
		{
			std::cout << 0 << '\n';
		}
		else
		{
			int l = tin[node], r = tout[node];
			l = lower_bound(Position.begin(), Position.end(), std::make_pair(l, 0)) - Position.begin();
			r = upper_bound(Position.begin(), Position.end(), std::make_pair(r, (int)1e9)) - Position.begin() - 1;
			std::cout << Get(1, 0, n - 1, l, r, suf) << '\n';
		}
	}
}

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