oj.uz

Submission #49991

# Submission time Handle Problem Language Result Execution time Memory
49991 2018-06-06T04:15:06 Z MatheusLealV Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 381 ms 220872 KB 
#include <bits/stdc++.h>
#define N 4000050
#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 107 ms 125692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 220872 KB Output is correct
2 Incorrect 152 ms 220872 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

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