Submission #535910

#	Time	Username	Problem	Language	Result	Execution time	Memory
535910		michao	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	363 ms	169784 KiB

selling_rna

#include <bits/stdc++.h>
//#define int long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAXN=1e5+5;
const int MAXT=2e6+5;
const int inf=(int)1e9+9;
string S[MAXN];
string P[MAXN];
string Q[MAXN];
int syn[MAXT][4];
int mini[MAXT];
int maxi[MAXT];
vi ids[MAXT];
int f(char x){
	if (x=='A')return 0;
	if (x=='G')return 1;
	if (x=='C')return 2;
	return 3;
}

int cnt=0;
pii przedzial[MAXN];

void update(int u,int x){
	mini[u]=min(mini[u],x);
	maxi[u]=max(maxi[u],x);
}	

void wstaw1(string s,int id){
	int u=0;
	update(u,id);
	for (auto it:s){
		int to=f(it);
		if (!syn[u][to])syn[u][to]=++cnt;
		u=syn[u][to];
		update(u,id);
	}
}

void wstaw2(string s,int id){
	int u=0;
	ids[u].pb(id);
	for (auto it:s){
		int to=f(it);
		if (!syn[u][to])syn[u][to]=++cnt;
		u=syn[u][to];
		ids[u].pb(id);
	}
}
pii search1(string s){
	int u=0;
	for (auto it:s){
		int to=f(it);
		if (!syn[u][to])return mp(inf,-inf);
		u=syn[u][to];
	}
	return mp(mini[u],maxi[u]);
}

vi search2(string s){
	int u=0;
	for (auto it:s){
		int to=f(it);
		if (!syn[u][to])return {};
		u=syn[u][to];
	}
	return ids[u];
}

int func(vi &v,int l,int r){
	if (l>r)return 0;
	if (v.empty())return 0;
	if (r<v[0] || l>v.back())return 0;
	auto itl=lower_bound(v.begin(),v.end(),l)-v.begin();
	auto itr=(--upper_bound(v.begin(),v.end(),r))-v.begin();
	return (int)itr-(int)itl+1;
}
int32_t main(){
  BOOST;
  fill(mini,mini+MAXT,inf);
  fill(maxi,maxi+MAXT,-inf);
  int n,m;
  cin>>n>>m;
  for (int i=1;i<=n;i++)cin>>S[i];
  sort(S+1,S+n+1);
  for (int i=1;i<=n;i++)wstaw1(S[i],i);
  for (int i=1;i<=m;i++){
		cin>>P[i]>>Q[i];
		przedzial[i]=search1(P[i]);
	}
	for (int i=0;i<MAXT;i++)for (int j=0;j<4;j++)syn[i][j]=0;
	cnt=0;
	for (int i=1;i<=n;i++){
		reverse(S[i].begin(),S[i].end());
		wstaw2(S[i],i);
	}
	for (int i=1;i<=m;i++){
		reverse(Q[i].begin(),Q[i].end());
		vi v=search2(Q[i]);
		cout<<func(v,przedzial[i].st,przedzial[i].nd)<<"\n";
	}
  return 0; 
}

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