제출 #839471

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
839471		anhduc2701	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	290 ms	359212 KiB

selling_rna

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second 
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int maxm=6e6+5;
map<char,int>m;
struct node{
	int a[4];
	int cnt=0;
	node(){for(int i=0;i<4;i++)a[i]=0;}
};
vector<node>trie[2];
int tin[2][maxm];
int tout[2][maxm];
int vt[2][maxm];
void add(string s,int id,int type){
	int pos=0;
	for(auto &v:s){
		int k=m[v];
		if(trie[type][pos].a[k]==0){
			trie[type][pos].a[k]=trie[type].size();
			trie[type].pb(node());
		}
		pos=trie[type][pos].a[k];
	}
	vt[type][id]=pos;
}
int s[2];
void dfs(int id,int type){
	tin[type][id]=++s[type];
	for(int pos=0;pos<4;pos++){
		if(trie[type][id].a[pos]!=0){
			dfs(trie[type][id].a[pos],type);
		}
	}
	tout[type][id]=s[type];
}
int n;
string p[2][maxn];
vector<int>Upd[maxm];
vector<int>poi;
int bit[maxn];
void update(int id,int val){
	for(int i=id;i<=n;i+=i&(-i)){
		bit[i]+=val;
	}
}
int get(int id){
	int res=0;
	for(int i=id;i>=1;i-=i&(-i)){
		res+=bit[i];
	}
	return res;
}
int getrange(int l,int r){
	return get(r)-get(l-1);
}
vector<pair<int,int>>P[maxm];
int ans[maxn];
int po2[maxn];
signed main(){
	// freopen("input.inp","r",stdin);
	// freopen("output.out","w",stdout);
	cin.tie(0),cout.tie(0)->sync_with_stdio(0);
	cin >> n;
	int q;
	cin >> q;
	trie[0].pb(node());
	trie[1].pb(node());
	m['A']=0;
	m['G']=1;
	m['C']=2;
	m['U']=3;
	for(int i=1;i<=n;i++){
		cin >> p[0][i];
		p[1][i]=p[0][i];
		reverse(p[1][i].begin(),p[1][i].end());
		add(p[0][i],i,0);
		add(p[1][i],i,1);
	}
	dfs(0,0);
	dfs(0,1);
	for(int i=1;i<=n;i++){
		poi.pb(tin[1][vt[1][i]]);
		Upd[tin[0][vt[0][i]]].pb(tin[1][vt[1][i]]);
	}
	sort(poi.begin(),poi.end());
	poi.resize(unique(poi.begin(),poi.end())-poi.begin());
	for(int i=1;i<=q;i++){
		string s;
		string p;
		int pos1=0;
		cin >> s >> p;
		bool loai=0;
		reverse(p.begin(),p.end());
		for(int j=0;j<(int)s.size();j++){
			if(trie[0][pos1].a[m[s[j]]]==0){
				loai=1;
				break;
			}
			else{
				pos1=trie[0][pos1].a[m[s[j]]];
			}
		}
		int pos2=0;
		for(int j=0;j<(int)p.size();j++){

			if(trie[1][pos2].a[m[p[j]]]==0){
				loai=1;
				break;
			}
			else{
				pos2=trie[1][pos2].a[m[p[j]]];
			}
		}
		if(loai==0){
			P[tin[0][pos1]-1].pb({i,-1});
			P[tout[0][pos1]].pb({i,1});
			po2[i]=pos2;
		}
	}
	for(int i=1;i<=s[0];i++){
		for(auto id:Upd[i]){
			int st=lower_bound(poi.begin(),poi.end(),id)-poi.begin()+1;
			update(st,1);
		}
		for(auto v:P[i]){
			int id=v.fi;
			int mul=v.se;
			int x=lower_bound(poi.begin(),poi.end(),tin[1][po2[id]])-poi.begin()+1;
			int y=upper_bound(poi.begin(),poi.end(),tout[1][po2[id]])-poi.begin();
			// cout << x << ' ' << y << '\n';
			ans[id]+=getrange(x,y)*mul;
		}
	}
	for(int i=1;i<=q;i++){
		cout << ans[i] << '\n';
	}
}

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