Submission #49995

#	Time	Username	Problem	Language	Result	Execution time	Memory
49995		MatheusLealV	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	417 ms	186208 KiB

selling_rna

#include <bits/stdc++.h>
#define N 2000050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int getid(char c)
{
	if(c == 'A') return 0;
	if(c == 'C') return 1;
	if(c == 'G') return 2;
	if(c == 'U') return 3;
}

struct node
{
	int ini, fim;

	node *prox[4];

	node(){
		for(int i = 0; i < 4; i++) prox[i] = NULL;
	}

} *T[2];

struct query
{
	int x, y, x2, tipo, id;
};

bool comp(query A, query B)
{
	if(A.y != B.y) return A.y < B.y;

	return A.tipo < B.tipo;
}

vector< pii > pontos;

vector< query > Q;

int n, m, cnt, ans[N];

string S[N];

void insert(node *root, string key)
{
	for(auto c: key)
	{
		int id = getid(c);

		if(!root->prox[id]) root->prox[id] = new node();

		root = root->prox[id];
	}
}

pii search(node *root, string key)
{
	for(auto c: key)
	{
		int id = getid(c);

		if(!root->prox[id]) return {-1, -1};

		root = root->prox[id];
	}

	return {root->ini, root->fim};
}

void dfs(node *root)
{
	root->ini = ++cnt;

	for(int i = 0; i < 4; i++)
	{
		if(!root->prox[i]) continue;

		dfs(root->prox[i]);
	}

	root->fim = cnt;
}

int bit[N];

void upd(int x, int v)
{
	for(int i = x; i < N; i += (i&-i)) bit[i] += v;
}

int query(int x)
{
	int sum = 0;

	for(int i = x; i > 0; i -= (i&-i)) sum += bit[i];

	return sum;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>m;

	T[0] = new node(), T[1] = new node();

	for(int i = 0; i < n; i++)
	{
		cin>>S[i];

		insert(T[0], S[i]);

		reverse(S[i].begin(), S[i].end());

		insert(T[1], S[i]);
	}

	dfs(T[0]), dfs(T[1]);

	for(int i = 0; i < n; i++)
	{
		int b = search(T[1], S[i]).f;

		reverse(S[i].begin(), S[i].end());

		int a = search(T[0], S[i]).f;

		Q.push_back( {a, b, a, 0, i} );
	}

	for(int i = 0; i < m; i++)
	{
		string pref, suf;

		cin>>pref>>suf;

		reverse(suf.begin(), suf.end());

		pii a = search(T[0], pref);

		pii b = search(T[1], suf);

		if(a.f == -1 || b.f == -1) continue;

		Q.push_back( {a.f, b.f - 1, a.s, 1, i} );

		Q.push_back( {a.f, b.s, a.s, 2, i} );
	}

	sort(Q.begin(), Q.end(), comp);

	for(int i = 0; i < Q.size(); i++)
	{
		if(!Q[i].tipo) upd(Q[i].x, +1);

		else
		{
			if(Q[i].tipo == 1) ans[ Q[i].id ] -= (query(Q[i].x2) - query(Q[i].x - 1));

			else ans[ Q[i].id ] += (query(Q[i].x2) - query(Q[i].x - 1));
		}
	}

	for(int i = 0; i < m; i++) cout<<ans[i]<<"\n";
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:157:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < Q.size(); i++)
                 ~~^~~~~~~~~~
selling_rna.cpp: In function 'int getid(char)':
selling_rna.cpp:14:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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