Submission #162596

#	Time	Username	Problem	Language	Result	Execution time	Memory
162596		HungAnhGoldIBO2020	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	858 ms	598848 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+2;
const int inf=1e9+7;
struct node{
	int go[26],l=0,r=0;
} pre[N];
struct node1{
	int go[26];
	vector<int> idx;
} suf[N];
pair<int,int> lis;
string x[N];
int cnt=0,cnt1=0;
void insert_pre(string s,int idx1){
	int now=0;
	for(int i=0;i<s.size();i++){
		if(!pre[now].go[(int)(s[i]-'A')]){
			cnt++;
			pre[now].go[(int)(s[i]-'A')]=cnt;
		}
		now=pre[now].go[(int)(s[i]-'A')];
		if(!pre[now].l){
			pre[now].l=idx1;
		}
		pre[now].r=idx1;
	}
}
void insert_suf(string s,int idx2){
	int now=0;
	for(int i=0;i<s.size();i++){
		if(!suf[now].go[(int)(s[i]-'A')]){
			cnt1++;
			suf[now].go[(int)(s[i]-'A')]=cnt1;
		}
		now=suf[now].go[(int)(s[i]-'A')];
		suf[now].idx.push_back(idx2);
	}
}
void get_range(string s){
	int now=0;
	for(int i=0;i<s.size();i++){
		if(!pre[now].go[(int)(s[i]-'A')]){
			lis.first=inf;
			lis.second=-inf;
			return;
		}
		now=pre[now].go[(int)(s[i]-'A')];
	}
	lis.first=pre[now].l;
	lis.second=pre[now].r;
}
int get_ans(string s){
	int now=0;
	for(int i=0;i<s.size();i++){
		if(!suf[now].go[(int)(s[i]-'A')]){
			return 0;
		}
		now=suf[now].go[(int)(s[i]-'A')];
	}
	int num1=upper_bound(suf[now].idx.begin(),suf[now].idx.end(),lis.second)-suf[now].idx.begin()-1;
	int num2=lower_bound(suf[now].idx.begin(),suf[now].idx.end(),lis.first)-suf[now].idx.begin()-1;
//	cout<<now<<" cac"<<endl;
//	for(int i:suf[now].idx){
//		cout<<i<<' ';
//	}
//	cout<<"lon "<<num1<<' '<<num2<<endl;
	return num1-num2;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,q,i,j,k,l;
	cin>>n>>q;
	for(i=1;i<=n;i++){
		cin>>x[i];
	}
	sort(x+1,x+1+n);
	string t,t1;
	for(i=1;i<=n;i++){
		t=x[i];
		insert_pre(t,i);
		reverse(t.begin(),t.end());
		insert_suf(t,i);
	}
	for(i=1;i<=q;i++){
		cin>>t>>t1;
		get_range(t);
		if(lis.second==-inf){
			cout<<"0\n";
			continue;
		}
		reverse(t1.begin(),t1.end());
		cout<<get_ans(t1)<<'\n';
	}
}

Compilation message (stderr)

selling_rna.cpp: In function 'void insert_pre(std::__cxx11::string, int)':
selling_rna.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.size();i++){
              ~^~~~~~~~~
selling_rna.cpp: In function 'void insert_suf(std::__cxx11::string, int)':
selling_rna.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.size();i++){
              ~^~~~~~~~~
selling_rna.cpp: In function 'void get_range(std::__cxx11::string)':
selling_rna.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.size();i++){
              ~^~~~~~~~~
selling_rna.cpp: In function 'int get_ans(std::__cxx11::string)':
selling_rna.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.size();i++){
              ~^~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:73:12: warning: unused variable 'j' [-Wunused-variable]
  int n,q,i,j,k,l;
            ^
selling_rna.cpp:73:14: warning: unused variable 'k' [-Wunused-variable]
  int n,q,i,j,k,l;
              ^
selling_rna.cpp:73:16: warning: unused variable 'l' [-Wunused-variable]
  int n,q,i,j,k,l;
                ^

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