oj.uz

Submission #366699

# Submission time Handle Problem Language Result Execution time Memory
366699 2021-02-15T04:50:44 Z Rainbowbunny Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 910 ms 614988 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 32236 KB Output is correct
2 Correct 43 ms 32236 KB Output is correct
3 Correct 45 ms 32364 KB Output is correct
4 Correct 43 ms 32236 KB Output is correct
5 Correct 42 ms 32236 KB Output is correct
6 Correct 42 ms 32236 KB Output is correct
7 Correct 48 ms 32364 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 872 ms 570852 KB Output is correct
2 Correct 910 ms 614988 KB Output is correct
3 Correct 531 ms 235552 KB Output is correct
4 Correct 531 ms 235884 KB Output is correct
5 Correct 791 ms 484036 KB Output is correct
6 Correct 804 ms 488204 KB Output is correct
7 Correct 263 ms 109164 KB Output is correct
8 Correct 643 ms 443588 KB Output is correct
9 Correct 590 ms 401624 KB Output is correct
10 Correct 509 ms 319284 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 40628 KB Output is correct
2 Correct 104 ms 40364 KB Output is correct
3 Correct 115 ms 39524 KB Output is correct
4 Correct 98 ms 37356 KB Output is correct
5 Correct 107 ms 39180 KB Output is correct
6 Correct 115 ms 39048 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 32236 KB Output is correct
2 Correct 43 ms 32236 KB Output is correct
3 Correct 45 ms 32364 KB Output is correct
4 Correct 43 ms 32236 KB Output is correct
5 Correct 42 ms 32236 KB Output is correct
6 Correct 42 ms 32236 KB Output is correct
7 Correct 48 ms 32364 KB Output is correct
8 Correct 872 ms 570852 KB Output is correct
9 Correct 910 ms 614988 KB Output is correct
10 Correct 531 ms 235552 KB Output is correct
11 Correct 531 ms 235884 KB Output is correct
12 Correct 791 ms 484036 KB Output is correct
13 Correct 804 ms 488204 KB Output is correct
14 Correct 263 ms 109164 KB Output is correct
15 Correct 643 ms 443588 KB Output is correct
16 Correct 590 ms 401624 KB Output is correct
17 Correct 509 ms 319284 KB Output is correct
18 Correct 108 ms 40628 KB Output is correct
19 Correct 104 ms 40364 KB Output is correct
20 Correct 115 ms 39524 KB Output is correct
21 Correct 98 ms 37356 KB Output is correct
22 Correct 107 ms 39180 KB Output is correct
23 Correct 115 ms 39048 KB Output is correct
24 Correct 855 ms 590964 KB Output is correct
25 Correct 871 ms 599008 KB Output is correct
26 Correct 836 ms 588336 KB Output is correct
27 Correct 572 ms 235656 KB Output is correct
28 Correct 706 ms 236224 KB Output is correct
29 Correct 410 ms 98528 KB Output is correct