Submission #1260330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260330		LM1	Selling RNA Strands (JOI16_selling_rna)	C++20	0 / 100	188 ms	172364 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define fr(i,ii,iii) for(int i=ii;i<iii;i++)
const int M=2e6+5;
int n,m;
string a[M];
map<char,int>mp={{'A',0},{'U',1},{'G',2},{'C',3}};
int trie[M][4][2],ct[2],id,idx,f[M][2];
pii p[M];
/*
id - prefix tu sufix trie
idx - indexi stringis
ct - tries gadanomrva
t1 - timer
f - am wveroze romeli sityva damtavrda
p - koordinatebi
*/
int in[M][2],out[M][2],t1;
struct qry{
	int tp,xx,yy,yy1,ind;
	bool operator<(const qry&oth)const{return xx<oth.xx;}
};
vector<qry>v;
int ans[M];
void ins(string s){
	int st=0;
	for(auto i:s){
		int &x=trie[st][mp[i]][id];
		if(x==0)x=++ct[id];
		st=x;
	}
	if(f[st][id]==0)f[st][id]=idx;
}
void dfs(int st){
	t1++;
	in[st][id]=t1;
	if(f[st][id]){
		if(id==0)p[f[st][id]].ff=t1;
		else p[f[st][id]].ss=t1;
	}
	fr(i,0,4){
		int x=trie[st][i][id];
		if(x!=0)dfs(x);
	}
	out[st][id]=t1;
}
pii fnd(string x){
	int st=0;
	for(auto i:x){
		if(trie[st][mp[i]][id]==0){
			return{-1,-1};
		}
		st=trie[st][mp[i]][id];
	}
	return{in[st][id],out[st][id]};
}
int fenw[2*M];
void addfenw(int x,int val){
	while(x<=2e6){
		fenw[x]+=val;
		x+= x & -x;
	}
}
int getfenw(int x){
	int s=0;
	while(x>=1){
		s+=fenw[x];
		x-= x & -x;
	}
	return s;
}
int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>m;
	fr(i,1,n+1){
		cin>>a[i];
		reverse(a[i].begin(),a[i].end());
		idx=i;
		id=1;ins(a[i]);
		reverse(a[i].begin(),a[i].end());
		id=0;ins(a[i]);
	}
	t1=-1;id=0;dfs(0);
	t1=-1;id=1;dfs(0);
	map<string,int>mp;
	fr(i,1,n+1){
		if(mp.count(a[i])){
			v.pb(v[mp[a[i]]]);
			continue;
		}
		v.pb({0,p[i].ff,p[i].ss,p[i].ss,-1});
		mp[a[i]]=v.size()-1;
	}
	fr(i,1,m+1){
		string aa,bb;cin>>aa>>bb;reverse(bb.begin(),bb.end());
		id=0;pii p1=fnd(aa);//pr
		id=1;pii p2=fnd(bb);//sf
		if(p1.ff==-1 or p2.ff==-1){
			continue;
		}
		v.pb({1,p1.ff-1,p2.ff,p2.ss,i});
		v.pb({2,p1.ss,p2.ff,p2.ss,i});
	}
	sort(v.begin(),v.end());
	for(auto i:v){
		if(i.tp==0){
			addfenw(i.yy,1);
		}
		else if(i.tp==1){
			ans[i.ind]-=getfenw(i.yy1)-getfenw(i.yy-1);
		}
		else{
			ans[i.ind]+=getfenw(i.yy1)-getfenw(i.yy-1);
		}
	}
	fr(i,1,m+1){
		cout<<ans[i];
		if(i!=m)cout<<"\n";
	}
}

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