Submission #1168524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168524		_rain_	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	144 ms	66376 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=(int)2e5;
const int MAXLOG=18;
pair<string,int> s[N+2];
string q[N+2];
int num=0;
int n,m;
int lcp[2*N+2][MAXLOG+2],LOG[N*2+2];
bool cmp(pair<string,int>&x1,pair<string,int>&x2){
	if (x1.first!=x2.first) return x1<x2;
	return x1.second<x2.second;
}
LL ans[N+2];

int Getmn(int l,int r){
	if (l>r) return 0;
	int x=LOG[r-l+1];
	return min(lcp[l][x],lcp[r-(1<<x)+1][x]);  
}

struct Node{
	int child[4]={};
	int cnt=0;
	Node(){
		memset(child,-1,sizeof child);
		cnt=0;
	}
};

int type(char x){
	if (x=='G') return 0;
	if (x=='U') return 1;
	if (x=='A') return 2;
	if (x=='C') return 3;
}

class Trie{
	public:
		vector<Node>v;
		void init(){
			v.push_back(Node());
		}
		void add(string &x,int addmore){
			int root=0;
			for(int i=0;i<x.size();++i){
				int c=type(x[i]);
				if (v[root].child[c]==-1) v[root].child[c]=v.size(),v.push_back(Node());
				v[root].cnt+=addmore;
				root=v[root].child[c];
			}
			v[root].cnt+=addmore;
		}
		
		int Find(string&x){
			int root=0;
			for(int i=0;i<x.size();++i){
				int c=type(x[i]);			
				if (v[root].child[c]==-1) return 0;
				root=v[root].child[c];
			}
			return v[root].cnt;
		}
};
Trie tree;
int Getlcp(int l,int r){
	if (l>r) swap(l,r);
	return Getmn(l+1,r);
}


	const int BLOCKSIZE=447;
	struct Mo_dtcl{
		int l,r,id;
		bool operator <(const Mo_dtcl&other) const{
			if (l/BLOCKSIZE!=other.l/BLOCKSIZE){
				return l/BLOCKSIZE<other.l/BLOCKSIZE;
			}
			return r<other.r;
		}
	};
	vector<Mo_dtcl> qs;


int Lower(int id,int need){
	int l=1,r=id-1,pos=id;
	while (l<=r){
		int m=(l+r)/2;
		if (Getlcp(m,id)!=need) l=m+1;
			else {
				pos=m;
				r=m-1;
			}
	}
	return pos;
}
int Upper(int id,int need){
	int l=id+1,r=num,pos=id;
	while (l<=r){
		int m=(l+r)/2;
		if (Getlcp(id,m)!=need) r=m-1;
			else {
				pos=m;
				l=m+1;
			}
	}
	return pos;
}

void cong(int id,int val){
	if (s[id].second==0) tree.add(s[id].first,val);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);

	cin>>n>>m;
	for(int i=1;i<=n;++i){
		string t; cin>>t;
		s[++num]={t,0};
	}
	for(int i=1;i<=m;++i){
		string t; cin>>t;
		cin>>q[i];
		reverse(q[i].begin(),q[i].end());
		s[++num]={t,i};
	}
	sort(s+1,s+num+1,cmp);
	lcp[1][0]=s[1].first.size();
	for(int i=2;i<=num;++i){
		for(int j=0;j<min(s[i-1].first.size(),s[i].first.size());++j){
			if (s[i-1].first[j]!=s[i].first[j]) break;
			lcp[i][0]++;
		}
	}
	for(int i=2;i<=num;++i) LOG[i]=LOG[i/2]+1;
	for(int j=1;j<=MAXLOG;++j){
		for(int i=1;i+(1<<j)-1<=num;++i) {
			lcp[i][j]=min(lcp[i][j-1],lcp[i+(1<<(j-1))][j-1]);
		}
	}

	for(int i=1;i<=num;++i) reverse(s[i].first.begin(),s[i].first.end());
	tree.init();
	for(int i=1;i<=num;++i){
		if (s[i].second!=0){
			int l=Lower(i,s[i].first.size());
			int r=Upper(i,s[i].first.size());
			qs.push_back({l,r,s[i].second});
		}
	}
	sort(qs.begin(),qs.end());
	int l=1,r=0;
	for(auto&x:qs){
		while (l<x.l) cong(l++,-1);
		while (l>x.l) cong(--l,1);
		while (r<x.r) cong(++r,1);
		while (r>x.r) cong(r--,-1);
		ans[x.id]=tree.Find(q[x.id]);
	}
	for(int i=1;i<=m;++i) cout<<ans[i]<<'\n';
}

Compilation message (stderr)

selling_rna.cpp: In function 'int type(char)':
selling_rna.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

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