oj.uz

Submission #49993

# Submission time Handle Problem Language Result Execution time Memory
49993 2018-06-06T04:30:44 Z MatheusLealV Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 386 ms 194856 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 - 1, 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 - 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

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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3556 KB Output is correct
3 Correct 5 ms 3764 KB Output is correct
4 Correct 5 ms 3764 KB Output is correct
5 Correct 6 ms 3864 KB Output is correct
6 Correct 5 ms 3864 KB Output is correct
7 Correct 5 ms 3864 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 98864 KB Output is correct
2 Correct 284 ms 98864 KB Output is correct
3 Runtime error 386 ms 194856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 194856 KB Output is correct
2 Correct 42 ms 194856 KB Output is correct
3 Correct 53 ms 194856 KB Output is correct
4 Correct 37 ms 194856 KB Output is correct
5 Correct 38 ms 194856 KB Output is correct
6 Correct 46 ms 194856 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3556 KB Output is correct
3 Correct 5 ms 3764 KB Output is correct
4 Correct 5 ms 3764 KB Output is correct
5 Correct 6 ms 3864 KB Output is correct
6 Correct 5 ms 3864 KB Output is correct
7 Correct 5 ms 3864 KB Output is correct
8 Correct 275 ms 98864 KB Output is correct
9 Correct 284 ms 98864 KB Output is correct
10 Runtime error 386 ms 194856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -