oj.uz

Submission #49989

# Submission time Handle Problem Language Result Execution time Memory
49989 2018-06-06T04:11:13 Z MatheusLealV Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 270 ms 102804 KB 
#include <bits/stdc++.h>
#define N 100050
#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} );

		//cout<<"PONTO "<<a<<" "<<b<<"\n";
	}

	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, a.s, 1, i} );

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

		//cout<<"QUERY "<<a.f<<" "<<a.s<<" "<<b.f<<" "<<b.s<<"\n";
	}

	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));

			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

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:161: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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 270 ms 102804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 102804 KB Output is correct
2 Incorrect 36 ms 102804 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3576 KB Output isn't correct
2 Halted 0 ms 0 KB -