oj.uz

Submission #304895

# Submission time Handle Problem Language Result Execution time Memory
304895 2020-09-22T07:26:00 Z EMEJ Selling RNA Strands (JOI16_selling_rna) C++11
100 / 100
 413 ms 183692 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 63096 KB Output is correct
2 Correct 42 ms 63096 KB Output is correct
3 Correct 44 ms 63096 KB Output is correct
4 Correct 42 ms 63096 KB Output is correct
5 Correct 43 ms 63096 KB Output is correct
6 Correct 42 ms 63096 KB Output is correct
7 Correct 42 ms 63104 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 162168 KB Output is correct
2 Correct 205 ms 157572 KB Output is correct
3 Correct 205 ms 161016 KB Output is correct
4 Correct 203 ms 156792 KB Output is correct
5 Correct 252 ms 182008 KB Output is correct
6 Correct 259 ms 183692 KB Output is correct
7 Correct 96 ms 70524 KB Output is correct
8 Correct 193 ms 139000 KB Output is correct
9 Correct 174 ms 128120 KB Output is correct
10 Correct 149 ms 123896 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 72184 KB Output is correct
2 Correct 94 ms 68600 KB Output is correct
3 Correct 101 ms 70392 KB Output is correct
4 Correct 81 ms 69240 KB Output is correct
5 Correct 81 ms 68676 KB Output is correct
6 Correct 93 ms 70392 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 63096 KB Output is correct
2 Correct 42 ms 63096 KB Output is correct
3 Correct 44 ms 63096 KB Output is correct
4 Correct 42 ms 63096 KB Output is correct
5 Correct 43 ms 63096 KB Output is correct
6 Correct 42 ms 63096 KB Output is correct
7 Correct 42 ms 63104 KB Output is correct
8 Correct 215 ms 162168 KB Output is correct
9 Correct 205 ms 157572 KB Output is correct
10 Correct 205 ms 161016 KB Output is correct
11 Correct 203 ms 156792 KB Output is correct
12 Correct 252 ms 182008 KB Output is correct
13 Correct 259 ms 183692 KB Output is correct
14 Correct 96 ms 70524 KB Output is correct
15 Correct 193 ms 139000 KB Output is correct
16 Correct 174 ms 128120 KB Output is correct
17 Correct 149 ms 123896 KB Output is correct
18 Correct 96 ms 72184 KB Output is correct
19 Correct 94 ms 68600 KB Output is correct
20 Correct 101 ms 70392 KB Output is correct
21 Correct 81 ms 69240 KB Output is correct
22 Correct 81 ms 68676 KB Output is correct
23 Correct 93 ms 70392 KB Output is correct
24 Correct 223 ms 146424 KB Output is correct
25 Correct 275 ms 146552 KB Output is correct
26 Correct 196 ms 145400 KB Output is correct
27 Correct 203 ms 145400 KB Output is correct
28 Correct 413 ms 97656 KB Output is correct
29 Correct 211 ms 84216 KB Output is correct