oj.uz

Submission #71900

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

#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:38: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 81 ms 94456 KB Output is correct
2 Correct 91 ms 94568 KB Output is correct
3 Correct 95 ms 94568 KB Output is correct
4 Correct 92 ms 94568 KB Output is correct
5 Correct 96 ms 94568 KB Output is correct
6 Correct 80 ms 94576 KB Output is correct
7 Correct 90 ms 94624 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 148132 KB Output is correct
2 Correct 424 ms 148132 KB Output is correct
3 Correct 454 ms 148132 KB Output is correct
4 Correct 411 ms 148132 KB Output is correct
5 Correct 417 ms 158408 KB Output is correct
6 Correct 407 ms 159292 KB Output is correct
7 Correct 318 ms 159292 KB Output is correct
8 Correct 487 ms 159292 KB Output is correct
9 Correct 407 ms 159292 KB Output is correct
10 Correct 345 ms 159292 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 159292 KB Output is correct
2 Correct 187 ms 159292 KB Output is correct
3 Correct 224 ms 159292 KB Output is correct
4 Correct 187 ms 159292 KB Output is correct
5 Correct 178 ms 159292 KB Output is correct
6 Correct 219 ms 159292 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 94456 KB Output is correct
2 Correct 91 ms 94568 KB Output is correct
3 Correct 95 ms 94568 KB Output is correct
4 Correct 92 ms 94568 KB Output is correct
5 Correct 96 ms 94568 KB Output is correct
6 Correct 80 ms 94576 KB Output is correct
7 Correct 90 ms 94624 KB Output is correct
8 Correct 359 ms 148132 KB Output is correct
9 Correct 424 ms 148132 KB Output is correct
10 Correct 454 ms 148132 KB Output is correct
11 Correct 411 ms 148132 KB Output is correct
12 Correct 417 ms 158408 KB Output is correct
13 Correct 407 ms 159292 KB Output is correct
14 Correct 318 ms 159292 KB Output is correct
15 Correct 487 ms 159292 KB Output is correct
16 Correct 407 ms 159292 KB Output is correct
17 Correct 345 ms 159292 KB Output is correct
18 Correct 270 ms 159292 KB Output is correct
19 Correct 187 ms 159292 KB Output is correct
20 Correct 224 ms 159292 KB Output is correct
21 Correct 187 ms 159292 KB Output is correct
22 Correct 178 ms 159292 KB Output is correct
23 Correct 219 ms 159292 KB Output is correct
24 Correct 371 ms 159292 KB Output is correct
25 Correct 455 ms 159292 KB Output is correct
26 Correct 364 ms 159292 KB Output is correct
27 Correct 356 ms 159292 KB Output is correct
28 Correct 756 ms 159292 KB Output is correct
29 Correct 680 ms 159292 KB Output is correct