Submission #399039

#	Time	Username	Problem	Language	Result	Execution time	Memory
399039		keta_tsimakuridze	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	399 ms	328644 KiB

selling_rna

#include<bits/stdc++.h>
#define f first
#define s second
#define ends endss
using namespace std;
const int N=1e5+5,mod=1e9+7;
int t,n,m,pwr[N],ans[N],tree[N],aft[40*N][5],cur,timer,L,R;
vector<pair<int,pair<int,int> > >Q[N],P[N];;
vector<int> ends[40*N][2];
string s[N],s1[N];
int get(char c){
	if(c=='A') return 1;
	if(c=='G') return 2;
	if(c=='U') return 3;
	return 0;
}
void add(string s,int ind,int f){
	int u = 0;
	for(int i=0;i<s.size();i++){
		if(!aft[u][get(s[i])]) cur++,aft[u][get(s[i])]=cur;
		
		u=aft[u][get(s[i])];	ends[u][f].push_back(ind);
	}

}
void find(string s){
	int u = 0;
	for(int i=0;i<s.size();i++){
		if(!aft[u][get(s[i])]) return;
		u=aft[u][get(s[i])];
	}	
	if(!ends[u][0].size()){
		L=n+1;
		R=0; return;
	}
	L = ends[u][0][0],R=ends[u][0].back();
}
void find1(string s,int ind){
	if(L>R) return ; 
	int u = 0;
	for(int i=0;i<s.size();i++){
		if(!aft[u][get(s[i])]) return;
		u=aft[u][get(s[i])];
	}

	int l=0,r=ends[u][1].size(),en=-1,st=n+1;r--;
	while(l<=r){
		int mid=(l+r)/2;
		if(ends[u][1][mid]>=L) {
			st=mid;
			r=mid-1;
		}
		else l=mid+1;
	}	
	 l=0,r=ends[u][1].size();r--;
	while(l<=r){
		int mid=(l+r)/2;
		if(ends[u][1][mid]<=R) {
			en=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	if(st<=en) 	ans[ind]=en-st+1;
}
 main(){
 	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	// t=1;
	cin >> n >> m;
	int mx = 0;
	for(int i=1;i<=n;i++){
		cin >> s[i];
	}
	sort(s+1,s+n+1); 
	for(int i=1;i<=n;i++){
		add(s[i],i,0); 
		reverse(s[i].begin(),s[i].end()); 
		add(s[i],i,1);
	}

	string pref,suff;
	for(int i=1;i<=m;i++){
	
		cin>>pref>>suff;
		L=n+1; R=0;
		find(pref);
		reverse(suff.begin(),suff.end());
	
		find1(suff,i);
	cout<<ans[i]<<" ";
	}
}

Compilation message (stderr)

selling_rna.cpp: In function 'void add(std::string, int, int)':
selling_rna.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0;i<s.size();i++){
      |              ~^~~~~~~~~
selling_rna.cpp: In function 'void find(std::string)':
selling_rna.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i=0;i<s.size();i++){
      |              ~^~~~~~~~~
selling_rna.cpp: In function 'void find1(std::string, int)':
selling_rna.cpp:41:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i=0;i<s.size();i++){
      |              ~^~~~~~~~~
selling_rna.cpp: At global scope:
selling_rna.cpp:66:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 |  main(){
      |       ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:70:6: warning: unused variable 'mx' [-Wunused-variable]
   70 |  int mx = 0;
      |      ^~

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