oj.uz

Submission #71899

# Submission time Handle Problem Language Result Execution time Memory
71899 2018-08-25T19:43:09 Z zadrga Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 832 ms 198708 KB 
/*
Idea:
- http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2016/2016-open-selling_rna-sol-en.pdf
*/

//5min + 21.12

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF ((int) 1e9)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 100011
#define maxch 2000111

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

int point[maxn][2], ans[maxn];
int adj[2][maxch][4], cnt[2], in[2][maxch], out[2][maxch];
int bit[maxch];
vector<int> leaf[2][maxch];
vector<vector<int> > q;

int val(char c){
	if(c == 'A')
		return 0;
	if(c == 'G')
		return 1;
	if(c == 'C')
		return 2;
	if(c == 'U')
		return 3;
}

void addTrie(int pos, int ind, string &s){
	int len = s.length();
	int x = 0;
	for(int i = 0; i < len; i++){
		int ch = val(s[i]);
		if(adj[pos][x][ch] == 0)
			adj[pos][x][ch] = ++cnt[pos];
		
		x = adj[pos][x][ch];
	}
	leaf[pos][x].pb(ind);
}

int findTrie(int pos, string &s){
	int len = s.length();
	int x = 0;
	for(int i = 0; i < len; i++){
		int ch = val(s[i]);
		if(adj[pos][x][ch] == 0)
			return -1;

		x = adj[pos][x][ch];
	}
	return x;
}

void DFS(int pos, int x){
	in[pos][x] = ++cnt[pos];
	for(int v : leaf[pos][x])
		point[v][pos] = cnt[pos];

	for(int i = 0; i < 4; i++){
		if(adj[pos][x][i])
			DFS(pos, adj[pos][x][i]);
	}
	out[pos][x] = cnt[pos];
}

void updateBIT(int x, int val){
	while(x < maxch){
		bit[x] += val;
		x += (x & -x);
	}
}

int sumBIT(int x){
	int ret = 0;
	while(x){
		ret += bit[x];
		x -= (x & -x);
	}
	return ret;
}

int main(){
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		string str;
		cin >> str;

		addTrie(0, i, str);
		reverse(str.begin(), str.end());
		addTrie(1, i, str);
	}

	cnt[0] = cnt[1] = 0;
	DFS(0, 0);
	DFS(1, 0);

	for(int i = 1; i <= n; i++)
		q.pb({point[i][0], point[i][1], -INF});

	for(int i = 1; i <= m; i++){
		string pre, suf;
		cin >> pre >> suf;
		reverse(suf.begin(), suf.end());
		
		int a = findTrie(0, pre);
		int b = findTrie(1, suf);

		if(a == -1 || b == -1)
			continue;

		q.pb({in[0][a] - 1, in[1][b] - 1, i});
		q.pb({in[0][a] - 1, out[1][b], -i});
		q.pb({out[0][a], in[1][b] - 1 , -i});
		q.pb({out[0][a], out[1][b] , i});
	}

	sort(q.begin(), q.end());

	for(vector<int> v : q){
		int pos = v[1];
		int ind = v[2];

		if(ind == -INF)
			updateBIT(pos, 1);
		
		else{
			int val = sumBIT(pos);
			if(ind > 0)
				ans[ind] += val;
			else
				ans[-ind] -= val;
		}
	}

	for(int i = 1; i <= m; i++)
		printf("%d\n", ans[i]);

	return 0;
}

Compilation message

selling_rna.cpp: In function 'int val(char)':
selling_rna.cpp:40: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 90 ms 94452 KB Output is correct
2 Correct 89 ms 94540 KB Output is correct
3 Correct 92 ms 94540 KB Output is correct
4 Correct 86 ms 94568 KB Output is correct
5 Correct 91 ms 94568 KB Output is correct
6 Correct 83 ms 94644 KB Output is correct
7 Correct 81 ms 94644 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 148456 KB Output is correct
2 Correct 363 ms 151552 KB Output is correct
3 Correct 405 ms 151552 KB Output is correct
4 Correct 383 ms 151768 KB Output is correct
5 Correct 383 ms 172680 KB Output is correct
6 Correct 399 ms 176188 KB Output is correct
7 Correct 305 ms 176188 KB Output is correct
8 Correct 437 ms 176188 KB Output is correct
9 Correct 424 ms 176188 KB Output is correct
10 Correct 319 ms 176188 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 176188 KB Output is correct
2 Correct 213 ms 176188 KB Output is correct
3 Correct 261 ms 176188 KB Output is correct
4 Correct 236 ms 176188 KB Output is correct
5 Correct 189 ms 176188 KB Output is correct
6 Correct 260 ms 176188 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 94452 KB Output is correct
2 Correct 89 ms 94540 KB Output is correct
3 Correct 92 ms 94540 KB Output is correct
4 Correct 86 ms 94568 KB Output is correct
5 Correct 91 ms 94568 KB Output is correct
6 Correct 83 ms 94644 KB Output is correct
7 Correct 81 ms 94644 KB Output is correct
8 Correct 416 ms 148456 KB Output is correct
9 Correct 363 ms 151552 KB Output is correct
10 Correct 405 ms 151552 KB Output is correct
11 Correct 383 ms 151768 KB Output is correct
12 Correct 383 ms 172680 KB Output is correct
13 Correct 399 ms 176188 KB Output is correct
14 Correct 305 ms 176188 KB Output is correct
15 Correct 437 ms 176188 KB Output is correct
16 Correct 424 ms 176188 KB Output is correct
17 Correct 319 ms 176188 KB Output is correct
18 Correct 272 ms 176188 KB Output is correct
19 Correct 213 ms 176188 KB Output is correct
20 Correct 261 ms 176188 KB Output is correct
21 Correct 236 ms 176188 KB Output is correct
22 Correct 189 ms 176188 KB Output is correct
23 Correct 260 ms 176188 KB Output is correct
24 Correct 399 ms 187844 KB Output is correct
25 Correct 557 ms 198708 KB Output is correct
26 Correct 365 ms 198708 KB Output is correct
27 Correct 384 ms 198708 KB Output is correct
28 Correct 832 ms 198708 KB Output is correct
29 Correct 660 ms 198708 KB Output is correct