Submission #304895

#	Time	Username	Problem	Language	Result	Execution time	Memory
304895		EMEJ	Selling RNA Strands (JOI16_selling_rna)	C++11	100 / 100	413 ms	183692 KiB

selling_rna

#include <bits/stdc++.h>

#define int long long
#define F first
#define S second
#define pb push_back
#define pii pair <int,int>
#define all(x) x.begin(),x.end()
#define SZ(x) (int)x.size()

using namespace std;

const int N=2e6+9,LG=22;
int nxt[2][N][4],cnt[2],ttt=0;
string s[N];
int id[2][N],st[2][N],ft[2][N];
pii arr[N];
int seg[LG][2*N];

int ADD(string t,int tt){
	int cur=0;
	for(int i=0;i<SZ(t);i++){
		if(nxt[tt][cur][t[i]-'A']){
			cur=nxt[tt][cur][t[i]-'A'];
		}
		else{
			nxt[tt][cur][t[i]-'A']=cnt[tt]++;
			cur=nxt[tt][cur][t[i]-'A'];
		}
	}
	return cur;
}

void DFS(int u,int tt){
	st[tt][u]=ttt++;
	for(int i=0;i<4;i++) if(nxt[tt][u][i]) DFS(nxt[tt][u][i],tt);
	ft[tt][u]=ttt;
}

int GO(string t,int tt){
	int cur=0;
	for(int i=0;i<SZ(t);i++){
		if(!nxt[tt][cur][t[i]-'A']) return -1;
		cur=nxt[tt][cur][t[i]-'A'];
	}
	return cur;
}

void BUILD(int l,int r,int h){
	if(l==r){
		seg[h][l]=arr[l].S;
		return ;
	}
	int mid=(l+r)/2;
	BUILD(l,mid,h+1);
	BUILD(mid+1,r,h+1);
	int ll=l,rr=mid+1,pos=l;
	while(ll<=mid && rr<=r){
		if(seg[h+1][ll]<seg[h+1][rr]){
			seg[h][pos]=seg[h+1][ll];
			ll++; pos++;
		}
		else{
			seg[h][pos]=seg[h+1][rr];
			pos++; rr++;
		}
	}
	while(ll<=mid) seg[h][pos++]=seg[h+1][ll++];
	while(rr<=r) seg[h][pos++]=seg[h+1][rr++];
}

int GET(int l,int r,int h,int ql,int qr,int mn,int mx){
	if(arr[l].F>qr || arr[r].F<ql) return 0;
	if(arr[l].F>=ql && arr[r].F<=qr){
		int num=lower_bound(seg[h]+l,seg[h]+r+1,mx)-lower_bound(seg[h]+l,seg[h]+r+1,mn);
		return num;
	}
	int mid=(l+r)/2;
	return GET(l,mid,h+1,ql,qr,mn,mx)+GET(mid+1,r,h+1,ql,qr,mn,mx);
}

int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n,q;
	cin>>n>>q;
	cnt[0]=cnt[1]=1;
	for(int i=0;i<n;i++){
		cin>>s[i];
		for(int j=0;j<SZ(s[i]);j++){
			if(s[i][j]=='G') s[i][j]='B';
			if(s[i][j]=='U') s[i][j]='D';
		}
		id[0][i]=ADD(s[i],0);
		reverse(all(s[i]));
		id[1][i]=ADD(s[i],1);
//		cout<<id[0][i]<<" "<<id[1][i]<<endl;
	}
	DFS(0,0);
	ttt=0;
	DFS(0,1);
	for(int i=0;i<n;i++){
		arr[i]={st[0][id[0][i]],st[1][id[1][i]]};
//		cout<<arr[i].F<<" "<<arr[i].S<<endl;
	}
	sort(arr,arr+n);
	BUILD(0,n-1,0);
	while(q--){
		string s1,s2;
		cin>>s1>>s2;
		reverse(all(s2));
		for(int j=0;j<SZ(s1);j++){
			if(s1[j]=='G') s1[j]='B';
			if(s1[j]=='U') s1[j]='D';
		}
		for(int j=0;j<SZ(s2);j++){
			if(s2[j]=='G') s2[j]='B';
			if(s2[j]=='U') s2[j]='D';
		}
		int id1=GO(s1,0),id2=GO(s2,1);
		if(id1==-1 || id2==-1){
			cout<<0<<'\n';
			continue ;
		}
		cout<<GET(0,n-1,0,st[0][id1],ft[0][id1]-1,st[1][id2],ft[1][id2])<<'\n';
	}
	return 0;
}

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