oj.uz

Submission #49995

# Submission time Handle Problem Language Result Execution time Memory
49995 2018-06-06T04:31:50 Z MatheusLealV Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 417 ms 186208 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 63 ms 62968 KB Output is correct
2 Correct 53 ms 63208 KB Output is correct
3 Correct 57 ms 63208 KB Output is correct
4 Correct 54 ms 63208 KB Output is correct
5 Correct 51 ms 63236 KB Output is correct
6 Correct 53 ms 63312 KB Output is correct
7 Correct 57 ms 63312 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 158416 KB Output is correct
2 Correct 289 ms 158416 KB Output is correct
3 Correct 318 ms 164048 KB Output is correct
4 Correct 288 ms 164048 KB Output is correct
5 Correct 374 ms 184212 KB Output is correct
6 Correct 417 ms 186208 KB Output is correct
7 Correct 133 ms 186208 KB Output is correct
8 Correct 299 ms 186208 KB Output is correct
9 Correct 258 ms 186208 KB Output is correct
10 Correct 232 ms 186208 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 186208 KB Output is correct
2 Correct 92 ms 186208 KB Output is correct
3 Correct 107 ms 186208 KB Output is correct
4 Correct 88 ms 186208 KB Output is correct
5 Correct 87 ms 186208 KB Output is correct
6 Correct 101 ms 186208 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 62968 KB Output is correct
2 Correct 53 ms 63208 KB Output is correct
3 Correct 57 ms 63208 KB Output is correct
4 Correct 54 ms 63208 KB Output is correct
5 Correct 51 ms 63236 KB Output is correct
6 Correct 53 ms 63312 KB Output is correct
7 Correct 57 ms 63312 KB Output is correct
8 Correct 322 ms 158416 KB Output is correct
9 Correct 289 ms 158416 KB Output is correct
10 Correct 318 ms 164048 KB Output is correct
11 Correct 288 ms 164048 KB Output is correct
12 Correct 374 ms 184212 KB Output is correct
13 Correct 417 ms 186208 KB Output is correct
14 Correct 133 ms 186208 KB Output is correct
15 Correct 299 ms 186208 KB Output is correct
16 Correct 258 ms 186208 KB Output is correct
17 Correct 232 ms 186208 KB Output is correct
18 Correct 104 ms 186208 KB Output is correct
19 Correct 92 ms 186208 KB Output is correct
20 Correct 107 ms 186208 KB Output is correct
21 Correct 88 ms 186208 KB Output is correct
22 Correct 87 ms 186208 KB Output is correct
23 Correct 101 ms 186208 KB Output is correct
24 Correct 278 ms 186208 KB Output is correct
25 Correct 316 ms 186208 KB Output is correct
26 Correct 284 ms 186208 KB Output is correct
27 Correct 322 ms 186208 KB Output is correct
28 Correct 306 ms 186208 KB Output is correct
29 Correct 179 ms 186208 KB Output is correct