Submission #59079

#	Time	Username	Problem	Language	Result	Execution time	Memory
59079		TadijaSebez	Selling RNA Strands (JOI16_selling_rna)	C++11	100 / 100	955 ms	556372 KiB

selling_rna

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;
#define pb push_back
const int H=100050;
const int N=2000050;
const int M=2*N;
map<char,int> go[M];
vector<int> my[M],all[H];
int tsz,root[2],lid[M],rid[M],tid,fir[M],las[M];
void Insert(int &c, int lvl, int n, char *s, int id)
{
	if(!c) c=++tsz;
	if(lvl==n){ my[c].pb(id);all[id].pb(c);return;}
	Insert(go[c][s[0]],lvl+1,n,s+1,id);
}
int Find(int c, int lvl, int n, char *s)
{
	if(lvl==n) return c;
	return Find(go[c][s[0]],lvl+1,n,s+1);
}
vector<int> ord;
int id[H];
void DFS1(int c)
{
	int i;
	map<char,int>::iterator it;
	fir[c]=ord.size()+1;
	for(i=0;i<my[c].size();i++) ord.pb(my[c][i]),id[my[c][i]]=ord.size();
	for(it=go[c].begin();it!=go[c].end();it++) DFS1(it->second);
	las[c]=ord.size();
}
void DFS2(int c)
{
	lid[c]=++tid;
	map<char,int>::iterator it;
	for(it=go[c].begin();it!=go[c].end();it++) DFS2(it->second);
	rid[c]=tid;
}
vector<int> push[M];
int ls[M],rs[M],rt,csz;
void Set(int &c, int ss, int se, int qi, int id)
{
	if(!c) c=++csz;
	push[c].pb(id);
	if(ss==se) return;
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[c],ss,mid,qi,id);
	else Set(rs[c],mid+1,se,qi,id);
}
int Get(int c, int l, int r)
{
	return upper_bound(push[c].begin(),push[c].end(),r)-lower_bound(push[c].begin(),push[c].end(),l);
}
int Get(int c, int ss, int se, int qs, int qe, int l, int r)
{
	if(qs>se || ss>qe) return 0;
	if(qs<=ss && qe>=se) return Get(c,l,r);
	int mid=ss+se>>1;
	return Get(ls[c],ss,mid,qs,qe,l,r)+Get(rs[c],mid+1,se,qs,qe,l,r);
}
char s[N],t[N];
int main()
{
	int n,q,i;
	scanf("%i %i",&n,&q);
	for(i=1;i<=n;i++)
	{
		scanf("%s",s);
		int len=strlen(s);
		Insert(root[0],0,len,s,i);
		reverse(s,s+len);
		Insert(root[1],0,len,s,i);
	}
	DFS1(root[0]);
	DFS2(root[1]);
	for(i=0;i<ord.size();i++)
	{
		int j=ord[i];
		Set(rt,1,N,lid[all[j].back()],id[j]);
		//printf("Set: %i -> %i\n",lid[all[j].back()],id[j]);
	}
	while(q--)
	{
		scanf("%s %s",s,t);
		int len1=strlen(s);
		int len2=strlen(t);
		reverse(t,t+len2);
		int node1=Find(root[0],0,len1,s);
		int node2=Find(root[1],0,len2,t);
		//printf("node1:%i node2:%i\n",node1,node2);
		//printf("Get: (%i %i) (%i %i)\n",lid[node2],rid[node2],fir[node1],las[node1]);
		printf("%i\n",Get(rt,1,N,lid[node2],rid[node2],fir[node1],las[node1]));
	}
	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void DFS1(int)':
selling_rna.cpp:32:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<my[c].size();i++) ord.pb(my[c][i]),id[my[c][i]]=ord.size();
          ~^~~~~~~~~~~~~
selling_rna.cpp: In function 'void Set(int&, int, int, int, int)':
selling_rna.cpp:50:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
selling_rna.cpp: In function 'int Get(int, int, int, int, int, int, int)':
selling_rna.cpp:62:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:80:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<ord.size();i++)
          ~^~~~~~~~~~~
selling_rna.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
selling_rna.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",s);
   ~~~~~^~~~~~~~
selling_rna.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s %s",s,t);
   ~~~~~^~~~~~~~~~~~~

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