제출 #598075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
598075		CSQ31	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	746 ms	1012844 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef pair<int,int> pii;
int ndcnt = 0;
const int MAXN = 8e6+5;
int ch[4][MAXN];
vector<int>ids[MAXN],que[MAXN],pts[MAXN];
int tin[MAXN],tout[MAXN];
pii pt[MAXN];
void add(string s,int id){
	int v = 0;
	for(char x:s){
		int c = 0;
		if(x=='C')c=1;
		if(x=='G')c=2;
		if(x=='U')c=3;
		if(!ch[c][v])ch[c][v] = ++ndcnt;
		v = ch[c][v];
	}
	ids[v].push_back(id);
}
int timer = 1;
void dfs(int v){
	tin[v] = ++timer;
	for(int i=0;i<4;i++){
		if(ch[i][v])dfs(ch[i][v]);
	}
	tout[v] = timer;
	for(int x:ids[v]){
		if(x>0)pt[x].fi = tin[v];
		else pt[-x].se = tin[v];
		
	}
	
}
int find(string s){
	int v = 0;
	for(char x:s){
		int c = 0;
		if(x=='C')c=1;
		if(x=='G')c=2;
		if(x=='U')c=3;
		if(!ch[c][v])return -1;
		v = ch[c][v];
	}
	return v;
	
}
int bit[MAXN];
void upd(int pos,int val,int n){
	for(int i=pos;i<=n;i+=i&(-i))bit[i]+=val;
}
int query(int r){
   int res = 0;
	for(int i=r;i>0;i-=i&(-i))res+=bit[i];
    return res;
}
int main()
{
	owo
	int n,m;
	cin>>n>>m;
	vector<string>s(n+1);
	vector<int>ans(m+1,0),l(m+1),r(m+1);
	for(int i=1;i<=n;i++){
		cin>>s[i];
		add(s[i],i);
		reverse(s[i].begin(),s[i].end());
		add(s[i],-i);
	}
	dfs(0);
	//cout<<"pts"<<'\n';
	for(int i=1;i<=n;i++){
		//cout<<pt[i].fi<<" "<<pt[i].se<<'\n';
		pts[pt[i].fi].push_back(pt[i].se);
	}
	//cout<<"frange"<<'\n';
	for(int i=1;i<=m;i++){
		string p,q;
		cin>>p>>q;
		int v1 = find(p);
		reverse(q.begin(),q.end());
		int v2 = find(q);
		//cout<<p<<" "<<q<<'\n';
		if(v1==-1 || v2==-1)continue;
		//cout<<v1<<" "<<v2<<'\n';
		//cout<<i<<" "<<tin[v1]<<" "<<tout[v1]<<" "<<tin[v2]<<" "<<tout[v2]<<'\n';
		l[i] = tin[v2]-1;
		r[i] = tout[v2];
		que[tin[v1]-1].push_back(-i);
		que[tout[v1]].push_back(i);
	}
	for(int i=1;i<=timer;i++){
		for(int x:pts[i])upd(x,1,timer);
		for(int x:que[i]){
			int c = query(r[abs(x)]) - query(l[abs(x)]);
			if(x>0)ans[x]+=c;
			else ans[x]-=c;
		}
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	
}

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