Submission #41516

#	Time	Username	Problem	Language	Result	Execution time	Memory
41516		kriii	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	719 ms	488976 KiB

selling_rna

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

const int maxn = 2000002;

map<char, int> trie[2][maxn];
vector<int> ends[2][maxn]; int cnt[2];
int L[2][maxn],R[2][maxn],A[2][maxn],I[maxn],C[2];

const int Z = 1<<20;
vector<int> IT[Z*2];

int N,M; char S[maxn];

void dfs(int k, int n)
{
	L[k][n] = C[k];
	for (auto &x : ends[k][n]) A[k][C[k]++] = x;
	for (auto &p : trie[k][n]) dfs(k,p.second);
	R[k][n] = C[k]-1;
}

int get(int i, int l, int r)
{
	return upper_bound(IT[i].begin(),IT[i].end(),r) - lower_bound(IT[i].begin(),IT[i].end(),l);
}

int query(int l, int r, int x, int y)
{
	int res = 0;
	x += Z; y += Z;
	while (x < y){
		if (x & 1) res += get(x++,l,r);
		if (~y & 1) res += get(y--,l,r);
		x /= 2; y /= 2;
	} if (x == y) res += get(x,l,r);
	return res;
}

int main()
{
	//freopen ("input.txt","r",stdin);

	scanf ("%d %d",&N,&M);
	for (int i=0;i<N;i++){
		scanf ("%s",S);
		int L = 0;
		while (S[L]) L++;
		for (int k=0;k<2;k++){
			int n = 0;
			for (int j=0;S[j];j++){
				int &nxt = trie[k][n][S[j]];
				if (!nxt) nxt = ++cnt[k];
				n = nxt;
			}
			ends[k][n].push_back(i);
			if (!k) reverse(S,S+L);
		}
	}

	for (int k=0;k<2;k++) dfs(k,0);
	for (int i=0;i<N;i++) I[A[0][i]] = i;
	for (int i=0;i<N;i++) A[1][i] = I[A[1][i]];
	for (int i=0;i<N;i++) I[A[1][i]] = i;
	for (int i=0;i<N;i++){
		int x = I[i] + Z;
		while (x){
			IT[x].push_back(i);
			x /= 2;
		}
	}

	for (int i=0;i<M;i++){
		int n[2] = {0,};
		for (int k=0;k<2;k++){
			scanf ("%s",S);
			if (k){
				int l = 0;
				while (S[l]) l++;
				reverse(S,S+l);
			}
			for (int j=0;S[j];j++){
				if (trie[k][n[k]].count(S[j])) n[k] = trie[k][n[k]][S[j]];
				else{n[k] = -1; break;}
			}
		}
		int ans;
		if (n[0] == -1 || n[1] == -1) ans = 0;
		else ans = query(L[0][n[0]],R[0][n[0]],L[1][n[1]],R[1][n[1]]);
		printf ("%d\n",ans);
	}

	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:47:23: 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:49:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%s",S);
                 ^
selling_rna.cpp:79:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf ("%s",S);
                  ^

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