Submission #1312683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312683		boclobanchat	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	405 ms	147480 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
const int MAXN=36e5+36;
const int INF=363636;
struct query { int t,l,r,pos; };
struct node { int child[4],atm[4],kmp,root,dep;bool ck;char c; };
struct nodet { int child[4],res,cnt; };
node trie[MAXN];
nodet T[MAXN];
vector<query> vq[MAXN];
vector<int> ds[MAXN];
int cnt=1,cntt=1,tdfs=0,td=0,P[MAXN/36],type[288],fen[MAXN],ans[MAXN/36],L[MAXN],R[MAXN],ll[MAXN],rr[MAXN],eul[MAXN];
string s[MAXN/36],p[MAXN/36],q[MAXN/36];
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
int get(int i) { int ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
void ins(string s,int i)
{
    int pos=1,pre=1;
    for(auto v:s)
    {
        if(!trie[pos].child[type[v]]) trie[pos].child[type[v]]=++cnt,trie[cnt].dep=trie[pos].dep+1;
        pre=pos,pos=trie[pos].child[type[v]],trie[pos].c=v,trie[pos].root=pre;
    }
    trie[P[i]=pos].ck=true;
}
int findatm(int pos,int c)
{
    if(trie[pos].atm[c]) return trie[pos].atm[c];
    if(trie[pos].child[c]) return trie[pos].atm[c]=trie[pos].child[c];
    if(pos==1) return trie[pos].atm[c]=1;
    return trie[pos].atm[c]=findatm(trie[pos].kmp,c);
}
void buildatm()
{
    queue<int> Q;
    Q.push(1);
    while(!Q.empty())
    {
        int pos=Q.front();
        Q.pop();
        if(pos==1||trie[pos].root==1) trie[pos].kmp=1;
        else
        {
            int p=trie[trie[pos].root].kmp,c=type[trie[pos].c];
            while(p!=1&&!trie[p].child[c]) p=trie[p].kmp;
            if(trie[p].child[c]) trie[pos].kmp=trie[p].child[c];
            else trie[pos].kmp=p;
        }
        for(int i=0;i<4;i++) if(trie[pos].child[i]) Q.push(trie[pos].child[i]);
    }
    for(int pos=1;pos<=cnt;pos++) for(int i=0;i<4;i++) trie[pos].atm[i]=findatm(pos,i);
    for(int pos=2;pos<=cnt;pos++) ds[trie[pos].kmp].push_back(pos);
}
void dfs(int i)
{
	L[i]=++tdfs;
	for(auto v:ds[i]) dfs(v);
	R[i]=tdfs;
}
void inst(string s,int i)
{
	int pos=1,res=1;
	T[pos].res=res;
	for(auto v:s)
	{
		if(!T[pos].child[type[v]]) T[pos].child[type[v]]=++cntt;
		pos=T[pos].child[type[v]],T[pos].res=res=trie[res].atm[type[v]];
	}
	T[pos].cnt++;
}
void dfs2(int i)
{
	ll[i]=++td,eul[td]=i;
	for(int j=0;j<4;j++) if(T[i].child[j]) dfs2(T[i].child[j]);
	rr[i]=td;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	type['A']=0,type['C']=1,type['G']=2,type['U']=3;
	int n,qq;
	cin>>n>>qq;
	for(int i=1;i<=n;i++) cin>>s[i];
	for(int i=1;i<=qq;i++)
	{
		cin>>p[i]>>q[i];
		ins(q[i],i);
	}
	buildatm();
	dfs(1);
	for(int i=1;i<=n;i++) inst(s[i],i);
	dfs2(1);
	for(int i=1;i<=qq;i++)
	{
		int pos=1;
		bool ck=true;
		for(auto v:p[i]) if(T[pos].child[type[v]]) pos=T[pos].child[type[v]];
		else
		{
			ck=false;
			break;
		}
		if(ck)
		{
			vq[ll[pos]-1].push_back({-1,L[P[i]],R[P[i]],i});
			vq[rr[pos]].push_back({1,L[P[i]],R[P[i]],i});
		}
	}
	for(int i=1;i<=cntt;i++)
	{
		update(L[T[eul[i]].res],cnt,T[eul[i]].cnt);
		for(auto v:vq[i]) ans[v.pos]+=v.t*(get(v.r)-get(v.l-1));
	}
	for(int i=1;i<=qq;i++) cout<<ans[i]<<"\n";
}

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