Submission #1280225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280225		WH8	Selling RNA Strands (JOI16_selling_rna)	C++20	Compilation error	0 ms	0 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
vector<vector<int>> to1(2000005,vector<int>(4, 0)), to2(2000005,vector<int>(4, 0));
vector<int> l1(2000005), r1(2000005);
vector<vector<int>> sm1(2000005), sm2(2000005);
vector<int> l2(2000005), r2(2000005), pos1(100005), pos2(100005), base(100005);

int mxn=100005, fw[100005];
void upd(int x, int v){
	if(x<=0)return;
	while(x<=mxn){
		fw[x]+=v;
		x+=(x&(-x));
	}
}
int qry(int x){
	//~ printf("qry %lld\n", x);
	//~ fflush(stdout);
	int ret=0;
	while(x>0){
		ret+=fw[x];
		x-=(x&(-x));
	}
	return ret;
}

int nw1=1, nw2=1;
signed main(){
	int n, m;cin>>n>>m;
	auto co=[&](char c) -> int {
		if(c=='A')return 0;
		else if(c=='U')return 1;
		else if(c=='G')return 2;
		else return 3;
	};
	for(int i=0;i<n;i++){
		string s;cin>>s;
		//~ cout<<"string " << s<<endl;
		int cur=0;
		int sz=s.size();
		for(int i=0;i<sz;i++){
			int nxt=co(s[i]);
			if(to1[cur][nxt]!=0)cur=to1[cur][nxt];
			else {
				to1[cur][nxt]=nw1;
				cur=nw1;
				nw1++;
			}
		}
		sm1[cur].push_back(i);
		cur=0;
		for(int i=sz-1;i>=0;i--){
			int nxt=co(s[i]);
			if(to2[cur][nxt]!=0){
				cur=to2[cur][nxt];
			}
			else {
				to2[cur][nxt]=nw2;
				cur=nw2;
				nw2++;
			}
		}
		sm2[cur].push_back(i);
	}
	int t=1;
	auto dfs = [&](auto&& dfs, int x,
				   const vector<vector<int>>& to,
				   vector<int>& l, vector<int>& r,
				   vector<vector<int>>& sm, vector<int> & pos) -> void {
		l[x]=t-1;
		for(auto it : sm[x]){
			pos[it]=t;
			t++;
		}
		for(int i=0;i<4;i++){
			if(to[x][i]!=0){
				dfs(dfs, to[x][i], to,l,r,sm,pos);
			}
		}
		r[x]=t-1;
		//~ printf("at %lld, l is %lld, r is %lld\n", x, l[x], r[x]);
	};
	dfs(dfs, 0, to1,l1,r1, sm1, pos1);
	t=1;
	//~ printf("dfs2 now. \n");
	dfs(dfs, 0, to2,l2,r2, sm2, pos2);
	vector<array<array<int,2>, 2>> qr(m);
	vector<int> ans(m, 0);
	vector<vector<pair<int,int>>> todo(n+1);
	for(int i=0;i<m;i++){
		string a,b;cin>>a>>b;
		int cur=0, done=0;
		for(auto c : a){
			int nxt=co(c);
			if(to1[cur][nxt]!=0)cur=to1[cur][nxt];
			else {
				qr[i][0][0]=-1;
				qr[i][0][1]=-1;
				done=1;
			}
		}
		if (!done) {
			qr[i][0][0]=l1[cur], qr[i][0][1]=r1[cur];
			//~ printf("qind %lld l1 %lld r1 %lld\n", i,qr[i][0][0], qr[i][0][1]);
		}
		cur=0, done=0;
		for(int i=(int)b.size()-1;i>=0;i--){
			int nxt=co(b[i]);
			if(to2[cur][nxt]!=0){
				cur=to2[cur][nxt];
			}
			else {
				qr[i][1][0]=-1;
				qr[i][1][1]=-1;
				done=1;
			}
		}
		if(!done) {
			qr[i][1][0]=l2[cur], qr[i][1][1]=r2[cur];
			todo[l2[cur]].push_back({i, 0});
			todo[r2[cur]].push_back({i, 1});
		}
		//~ printf("query index %lld, 1range %lld to %lld, 2range %lld to %lld\n", i, qr[i][0][0], qr[i][0][1], qr[i][1][0],qr[i][1][1]);
	}
	
	for(int i=0;i<n;i++){
		//~ printf("string index %lld, pos1 %lld, pos2 %lld\n", i,pos1[i], pos2[i]);
		base[pos2[i]]=pos1[i];
	}
	
	//~ for(int i=1;i<=n;i++){
		//~ printf("base %lld =  %lld \n", i, base[i]);
	//~ }
	//~ return 0;
	for(int i=1;i<=n;i++){
		//~ printf("upd %lld\n", pos1[i]);
		//~ fflush(stdout);
		//~ cout<<endl<<i<<endl;
		upd(base[i], 1);
		for(auto [qind, type] : todo[i]){
			//~ printf("qind %lld, type %lld, r %lld, l %lld, up %lld , down %lld\n", qind, type,qr[qind][0][1],qr[qind][0][0], qry(qr[qind][0][1]), qry(qr[qind][0][0]));
			int res=qry(qr[qind][0][1]) - qry(qr[qind][0][0]);
			if(type==0)ans[qind]-=res;
			else ans[qind]+=res;
		}
	}
	for(int i=0;i<m;i++){
		cout<<ans[i]<<"\n";
	}
}