oj.uz

Submission #209659

# Submission time Handle Problem Language Result Execution time Memory
209659 2020-03-15T03:19:53 Z AQT Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 126 ms 96120 KB 
#include <bits/stdc++.h>

using namespace std;

int N, Q;
string s;
int trief[4][2000005];
int trier[4][2000005];
int cntf = 0, cntr = 0;
int lftf[2000005], rhtf[2000005];
int lftr[2000005], rhtr[2000005];
int totf[2000005], totr[2000005];
int pf[200005], pr[200005];
int t = 0;
int qf[200005], qr[200005];
int who[200005];
int bit[4000005];
vector<int> qu[200005], add[200005];
int ans[200005];

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

void dfs1(int n){
	lftf[n] = ++t;
	for(int k = 3; k>=0; k--){
		if(trief[k][n]){
			dfs1(trief[k][n]);
		}
	}
	rhtf[n] = ++t;
}

void dfs2(int n){
	lftr[n] = ++t;
	for(int k = 3; k>=0; k--){
		if(trier[k][n]){
			dfs2(trier[k][n]);
		}
	}
	rhtr[n] = ++t;
}

void upd(int n){
	while(n <= 2*cntr+2){
		bit[n]++;
		n += n&-n;
	}
}

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

void dfs3(int n){
	for(int q : qu[n]){
		//cout << "f " << rhtr[qr[q]] << " " << lftr[qr[q]] << "\n";
		ans[q] -= query(rhtr[qr[q]]) - query(lftr[qr[q]]-1);
	}
	for(int k = 3; k>=0; k--){
		if(trief[k][n]){
			dfs3(trief[k][n]);
		}
	}
	for(int a : add[n]){
		//cout << lftr[who[a]] << "\n";
		upd(rhtr[who[a]]);
	}
	for(int q : qu[n]){
		//cout << rhtr[qr[q]] << " " << lftr[qr[q]] << "\n";
		//cout << query(rhtr[qr[q]]) << " " << query(lftr[qr[q]]) << "\n";
		ans[q] += query(rhtr[qr[q]]) - query(lftr[qr[q]]-1);
	}
}

int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> Q;
	for(int i = 1; i<=N; i++){
		cin >> s;
		int n = 0;
		for(char c : s){
			int k = getc(c);
			if(!trief[k][n]){
				trief[k][n] = ++cntf;
			}
			n = trief[k][n];
		}
		add[n].emplace_back(i);
		totf[n]++;
		n = 0;
		reverse(s.begin(), s.end());
		for(char c : s){
			int k = getc(c);
			if(!trier[k][n]){
				trier[k][n] = ++cntr;
			}
			n = trier[k][n];
		}
		totr[n]++;
		who[i] = n;
	}
	//cout << cntf << " " << cntr << "\n";
	/*
	for(int k : add[1]){
		cout << k << " ";
	}
	cout << "\n";
	*/
	dfs1(0);
	t = 0;
	dfs2(0);
	for(int i = 1; i<=Q; i++){
		cin >> s;
		int n = 0;
		bool b = 1;
		for(char c : s){
			int k = getc(c);
			if(trief[k][n]){
				n = trief[k][n];
			}
			else{
				b = 0;
				break;
			}
		}
		qf[i] = n;
		n = 0;
		cin >> s;
		if(!b){
			continue;
		}
		reverse(s.begin(), s.end());
		for(char c : s){
			int k = getc(c);
			if(trier[k][n]){
				n = trier[k][n];
			}
			else{
				b = 0;
				break;
			}
		}
		qr[i] = n;
		if(b){
			qu[qf[i]].emplace_back(i);	
		}
	}
	dfs3(0);
	for(int q = 1; q<=Q; q++){
		cout << ans[q] << "\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Correct 10 ms 9848 KB Output is correct
3 Correct 10 ms 9848 KB Output is correct
4 Correct 10 ms 9848 KB Output is correct
5 Correct 10 ms 9848 KB Output is correct
6 Correct 11 ms 9848 KB Output is correct
7 Correct 10 ms 9848 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 71092 KB Output is correct
2 Correct 116 ms 73720 KB Output is correct
3 Runtime error 126 ms 96120 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 30 ms 11512 KB Output is correct
2 Correct 27 ms 11000 KB Output is correct
3 Correct 31 ms 11388 KB Output is correct
4 Correct 24 ms 11260 KB Output is correct
5 Correct 35 ms 11408 KB Output is correct
6 Correct 30 ms 11512 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Correct 10 ms 9848 KB Output is correct
3 Correct 10 ms 9848 KB Output is correct
4 Correct 10 ms 9848 KB Output is correct
5 Correct 10 ms 9848 KB Output is correct
6 Correct 11 ms 9848 KB Output is correct
7 Correct 10 ms 9848 KB Output is correct
8 Correct 119 ms 71092 KB Output is correct
9 Correct 116 ms 73720 KB Output is correct
10 Runtime error 126 ms 96120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -