oj.uz

Submission #59079

# Submission time Handle Problem Language Result Execution time Memory
59079 2018-07-20T12:18:13 Z TadijaSebez Selling RNA Strands (JOI16_selling_rna) C++11
100 / 100
 955 ms 556372 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 378696 KB Output is correct
2 Correct 387 ms 378872 KB Output is correct
3 Correct 368 ms 378872 KB Output is correct
4 Correct 407 ms 378872 KB Output is correct
5 Correct 339 ms 378872 KB Output is correct
6 Correct 319 ms 378876 KB Output is correct
7 Correct 323 ms 378876 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 841 ms 500796 KB Output is correct
2 Correct 710 ms 504000 KB Output is correct
3 Correct 955 ms 509392 KB Output is correct
4 Correct 857 ms 509956 KB Output is correct
5 Correct 807 ms 551788 KB Output is correct
6 Correct 748 ms 556372 KB Output is correct
7 Correct 510 ms 556372 KB Output is correct
8 Correct 826 ms 556372 KB Output is correct
9 Correct 910 ms 556372 KB Output is correct
10 Correct 677 ms 556372 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 556372 KB Output is correct
2 Correct 451 ms 556372 KB Output is correct
3 Correct 485 ms 556372 KB Output is correct
4 Correct 451 ms 556372 KB Output is correct
5 Correct 456 ms 556372 KB Output is correct
6 Correct 474 ms 556372 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 378696 KB Output is correct
2 Correct 387 ms 378872 KB Output is correct
3 Correct 368 ms 378872 KB Output is correct
4 Correct 407 ms 378872 KB Output is correct
5 Correct 339 ms 378872 KB Output is correct
6 Correct 319 ms 378876 KB Output is correct
7 Correct 323 ms 378876 KB Output is correct
8 Correct 841 ms 500796 KB Output is correct
9 Correct 710 ms 504000 KB Output is correct
10 Correct 955 ms 509392 KB Output is correct
11 Correct 857 ms 509956 KB Output is correct
12 Correct 807 ms 551788 KB Output is correct
13 Correct 748 ms 556372 KB Output is correct
14 Correct 510 ms 556372 KB Output is correct
15 Correct 826 ms 556372 KB Output is correct
16 Correct 910 ms 556372 KB Output is correct
17 Correct 677 ms 556372 KB Output is correct
18 Correct 452 ms 556372 KB Output is correct
19 Correct 451 ms 556372 KB Output is correct
20 Correct 485 ms 556372 KB Output is correct
21 Correct 451 ms 556372 KB Output is correct
22 Correct 456 ms 556372 KB Output is correct
23 Correct 474 ms 556372 KB Output is correct
24 Correct 806 ms 556372 KB Output is correct
25 Correct 830 ms 556372 KB Output is correct
26 Correct 711 ms 556372 KB Output is correct
27 Correct 739 ms 556372 KB Output is correct
28 Correct 855 ms 556372 KB Output is correct
29 Correct 571 ms 556372 KB Output is correct