oj.uz

Submission #49990

# Submission time Handle Problem Language Result Execution time Memory
49990 2018-06-06T04:13:55 Z MatheusLealV Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 138236 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)
		{
			cout<<"0\n";

			continue;
		}

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

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

		int teste = 0;

		for(int i = 0; i < Q.size(); i++)
		{
			int x = Q[i].x, y = Q[i].y;

			if(a.f <= x && x <= a.s && b.f <= y && y <= b.s) teste ++;
		}

		cout<<teste<<"\n";

		//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:163:20: 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3572 KB Output is correct
3 Correct 4 ms 3572 KB Output is correct
4 Correct 4 ms 3652 KB Output is correct
5 Correct 4 ms 3672 KB Output is correct
6 Correct 5 ms 3672 KB Output is correct
7 Correct 5 ms 3672 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 98772 KB Output is correct
2 Correct 415 ms 98772 KB Output is correct
3 Correct 336 ms 105256 KB Output is correct
4 Correct 409 ms 105256 KB Output is correct
5 Correct 545 ms 134116 KB Output is correct
6 Correct 450 ms 138236 KB Output is correct
7 Correct 124 ms 138236 KB Output is correct
8 Correct 354 ms 138236 KB Output is correct
9 Correct 326 ms 138236 KB Output is correct
10 Correct 203 ms 138236 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1561 ms 138236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3572 KB Output is correct
3 Correct 4 ms 3572 KB Output is correct
4 Correct 4 ms 3652 KB Output is correct
5 Correct 4 ms 3672 KB Output is correct
6 Correct 5 ms 3672 KB Output is correct
7 Correct 5 ms 3672 KB Output is correct
8 Correct 290 ms 98772 KB Output is correct
9 Correct 415 ms 98772 KB Output is correct
10 Correct 336 ms 105256 KB Output is correct
11 Correct 409 ms 105256 KB Output is correct
12 Correct 545 ms 134116 KB Output is correct
13 Correct 450 ms 138236 KB Output is correct
14 Correct 124 ms 138236 KB Output is correct
15 Correct 354 ms 138236 KB Output is correct
16 Correct 326 ms 138236 KB Output is correct
17 Correct 203 ms 138236 KB Output is correct
18 Execution timed out 1561 ms 138236 KB Time limit exceeded
19 Halted 0 ms 0 KB -