Submission #26515

#	Time	Username	Problem	Language	Result	Execution time	Memory
26515		rubabredwan	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	193 ms	610552 KiB

selling_rna

/*  Bismillahir Rahmanir Rahim  */

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
const int M = 2000005;

int mp[M], from[M];
int cc[N];

struct TRIE{

	int trie[M][4];
	int in[M], out[M], cnt[M];
	int idx, t;

	void init(){
		memset(cnt, 0, sizeof(cnt));
		memset(trie, 0, sizeof(trie));
		idx = 1;
		t = 0;
	}

	int insert(string str, int ot){
		int cur = 1;
		for(auto u : str){
			int c = cc[u];
			if(trie[cur][c] == 0) trie[cur][c] = ++idx;
			cur = trie[cur][c];
		}
		from[cur] = ot;
		++cnt[cur];
		return cur;
	}

	int query(string str){
		int cur = 1;
		for(auto u : str){
			int c = cc[u];
			if(trie[cur][c] == 0) return -1;
			cur = trie[cur][c];
		}
		return cur;
	}

	void dfs(int at){
		in[at] = ++t;
		mp[t] = at;
		for(int c = 0; c <= 3; ++c){
			if(trie[at][c]){
				dfs(trie[at][c]);
			}
		}
		out[at] = t;
	}

};

int n, m, k;
int nn, mm;
string rna[N];
TRIE t1, t2;
int id1[N], id2[N];

int root[M];
int lf[20 * M], rf[20 * M];
int sum[20 * M];
int idx;

int update(int b, int e, int node, int pos, int val){
	int cur = ++idx;
	sum[cur] = sum[node] + val;
	if(b == e) return cur;
	int mid = (b + e) / 2;
	lf[cur] = lf[node];
	rf[cur] = rf[node];
	if(pos <= mid) lf[cur] = update(b, mid, lf[node], pos, val);
	else rf[cur] = update(mid + 1, e, rf[node], pos, val);
	return cur;
}

int get(int b, int e, int node, int x, int y){
	if(y < b || e < x || node == 0) return 0;
	if(b >= x && e <= y) return sum[node];
	int mid = (b + e) / 2;
	return get(b, mid, lf[node], x, y) + get(mid + 1, e, rf[node], x, y);
}

void init(){
	cc['A'] = 0;
	cc['C'] = 1;
	cc['G'] = 2;
	cc['U'] = 3;
	t1.init();
	t2.init();
	for(int i = 1; i <= n; ++i){
		id1[i] = t1.insert(rna[i], 0);
	}	
	t1.dfs(1);
	nn = t1.idx;
	for(int i = 1; i <= n; ++i) reverse(rna[i].begin(), rna[i].end());
	for(int i = 1; i <= n; ++i){
		id2[i] = t2.insert(rna[i], t1.in[ id1[i] ]);
	}	
	t2.dfs(1);
	mm = t2.idx;
	for(int i = 1; i <= mm; ++i){
		int at = mp[i];
		if(from[at] == 0) root[i] = root[i-1];
		else{
			root[i] = update(1, nn, root[i-1], from[at], t2.cnt[at]);
		}
	}
}

int query(string p, string q){
	int a = t1.query(p);
	reverse(q.begin(), q.end());
	int b = t2.query(q);
	if(a == -1 || b == -1) return 0;
	int aa = get(1, nn, root[ t2.out[b] ], t1.in[a], t1.out[a]);
	int bb = get(1, nn, root[ t2.in[b] - 1 ], t1.in[a], t1.out[a]);
	return aa - bb;
}

char str[N], p[N], q[N];

int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; ++i){
		scanf("%s", str);
		rna[i] = (string)(str);
	}
	init();
	for(int i = 1; i <= m; ++i){
		scanf("%s", p);
		scanf("%s", q);
		cout << query(p, q) << '\n';
	}
	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In member function 'int TRIE::insert(std::__cxx11::string, int)':
selling_rna.cpp:29:16: warning: array subscript has type 'char' [-Wchar-subscripts]
    int c = cc[u];
                ^
selling_rna.cpp: In member function 'int TRIE::query(std::__cxx11::string)':
selling_rna.cpp:41:16: warning: array subscript has type 'char' [-Wchar-subscripts]
    int c = cc[u];
                ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:131:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
selling_rna.cpp:133:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", str);
                   ^
selling_rna.cpp:138:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", p);
                 ^
selling_rna.cpp:139:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", q);
                 ^

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40