Submission #343260

#	Time	Username	Problem	Language	Result	Execution time	Memory
343260		mp007mp	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	1199 ms	132584 KiB

selling_rna

#include<bits/stdc++.h>
#define S second
#define F first
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
int inf = 1e9;
const int maxn = 1e5+20;
vector<string> vec;
vector<string> tmp;
vector<string> seg[maxn*4];
string nxt(string s){
	int n = s.size();
	string t=s;
	t[n-1]++;
	return t;
}
void RVR(string&s){
	int n = s.size();
	for(int i=0,j=n-1;i < j;i++,j--){
		swap(s[i],s[j]);
	}
}
void build(int s,int e,int v){
	if(e-s<2){
		seg[v].push_back(tmp[s]);
		return;
	}
	int mid = (s+e)/2;
	build(s,mid,2*v);
	build(mid,e,2*v+1);
	int l=0,r=0;
	while(l<seg[2*v].size() || r<seg[2*v+1].size()){
		if(l>=seg[2*v].size() || (r<seg[2*v+1].size() && seg[2*v+1][r]<=seg[2*v][l])){
			seg[v].push_back(seg[2*v+1][r]);
			r++;
		}else{
			seg[v].push_back(seg[2*v][l]);
			l++;
		}
	}
}
int ans(int s,int e,int v,int l,int r,string ll,string rr){
	if(l<=s && e<=r){
		return lower_bound(seg[v].begin(),seg[v].end(),rr)-lower_bound(seg[v].begin(),seg[v].end(),ll);
	}
	if(l>=e || s>=r){
		return 0;
	}
	int mid = (s+e)/2;
	return ans(s,mid,2*v,l,r,ll,rr)+ans(mid,e,2*v+1,l,r,ll,rr);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		vec.push_back(s);
	}
	sort(vec.begin(),vec.end());
	for(string s:vec){
		RVR(s);
		tmp.push_back(s);
	}
	int sz = tmp.size();
	build(0,sz,1);
	for(int i=0;i<m;i++){
		string p,q;
		cin>>p>>q;
		int l = lower_bound(vec.begin(),vec.end(),p)-vec.begin();
		int r = lower_bound(vec.begin(),vec.end(),nxt(p))-vec.begin();
		RVR(q);
		//cout<<l<<" "<<r<<"\n";
		cout<<ans(0,sz,1,l,r,q,nxt(q))<<"\n";
	}


	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void build(int, int, int)':
selling_rna.cpp:33:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  while(l<seg[2*v].size() || r<seg[2*v+1].size()){
      |        ~^~~~~~~~~~~~~~~~
selling_rna.cpp:33:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  while(l<seg[2*v].size() || r<seg[2*v+1].size()){
      |                             ~^~~~~~~~~~~~~~~~~~
selling_rna.cpp:34:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   if(l>=seg[2*v].size() || (r<seg[2*v+1].size() && seg[2*v+1][r]<=seg[2*v][l])){
      |      ~^~~~~~~~~~~~~~~~~
selling_rna.cpp:34:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   if(l>=seg[2*v].size() || (r<seg[2*v+1].size() && seg[2*v+1][r]<=seg[2*v][l])){
      |                             ~^~~~~~~~~~~~~~~~~~

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