Submission #598051

#	Time	Username	Problem	Language	Result	Execution time	Memory
598051		CSQ31	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1577 ms	53172 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> pii;
const int MOD1 = 1e9+7;
const int MOD2 = 998244353;
pii make_hash(string s){
	int n = s.size();
	int z1 = 5;
	int z2 = 5;
	pii hb = {0,0};
	for(int i=0;i<n;i++){
		int c = 1;
		if(s[i] == 'c')c=2;
		else if(s[i] == 'g')c=3;
		else if(s[i] == 'u')c=4;
		hb.fi += c * 1LL * z1%MOD1;
		hb.se += c * 1LL * z2%MOD2;
		if(hb.fi>=MOD1)hb.fi-=MOD1;
		if(hb.se>=MOD2)hb.se-=MOD2;
		
		z1 = z1 * 1LL * 5 %MOD1;
		z2 = z2 * 1LL * 5 %MOD2;
	}
	return hb;
}
int cmp(string &a,string &b){
	int n = a.size();
	int m = b.size();
	for(int i=0;i<n;i++){
		if(i==m)return 2;
		if(b[i] > a[i])return 0; //a is smaller 
		if(a[i] > b[i])return 2; //a is bigger
	}
	return 1;
}
vector<int>sa(string s){
	s+="`";
	int n = s.size();
	vector<int>p(n),c(n),cnt(27);
	for(int i=0;i<n;i++)cnt[s[i]-'`']++;
	for(int i=1;i<=26;i++)cnt[i]+=cnt[i-1];
	for(int i=0;i<n;i++)p[--cnt[s[i]-'`']] = i;
	c[p[0]] = 0;
	int cas = 1;
	for(int i=1;i<n;i++){
		if(s[p[i]] != s[p[i-1]])cas++;
		c[p[i]] = cas-1;
	}
	vector<int>pn(n),cn(n);
	for(int k=0;(1<<k)<n;k++){
		//we want to sort by pairs of class {x,y}
		for(int i=0;i<n;i++){ //this auto sorts it by y first
			pn[i] = p[i] - (1<<k);
			if(pn[i] <0)pn[i]+=n;
		}
		cnt.assign(cas,0);
		for(int i=0;i<n;i++)cnt[c[i]]++;
		for(int i=1;i<cas;i++)cnt[i]+=cnt[i-1];
		//counting sort /stable sort on first coord
		for(int i=n-1;i>=0;i--){
			p[--cnt[c[pn[i]]]] = pn[i];
		}
		cn[p[0]] = 0;
		cas = 1;
		for(int i=1;i<n;i++){
			pii a = {c[p[i-1]] , c[(p[i-1] + (1<<k))%n]};
			pii b = {c[p[i]] , c[(p[i] + (1<<k))%n]};
			if(a != b)cas++;
			cn[p[i]] = cas-1;
		}
		swap(cn,c);
	}
	return p;
}
int has[2000001];
const int segsz = 2e7;
int ndcnt = 0;
int cnt[segsz];
int ch[2][segsz];
int upd(int v,int pos,int l,int r){
	int nw = ++ndcnt;
	if(l==r){
		cnt[nw] = cnt[v]+1;
		return nw;
	}
	int tm = (l+r)/2;
	cnt[nw] = cnt[v]+1;
	if(pos<=tm){
		if(!ch[0][v])ch[0][v] = ++ndcnt;
		ch[1][nw] = ch[1][v];
		ch[0][nw] = upd(ch[0][v],pos,l,tm);
	}
	else{
		if(!ch[1][v])ch[1][v] = ++ndcnt;
		ch[0][nw] = ch[0][v];
		ch[1][nw] = upd(ch[1][v],pos,tm+1,r);
	}
	return nw;
}
int query(int v,int l,int r,int pos){
	if(!v)return 0;
	if(l==r)return cnt[v];
	int tm = (l+r)/2;
	if(pos<=tm)return query(ch[0][v],l,tm,pos);
	else return query(ch[1][v],tm+1,r,pos);
	
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,m;
	cin>>n>>m;
	vector<string>s(n);
	for(int i=0;i<n;i++){
		cin>>s[i];
		for(char &x:s[i])x+='a'-'A';
	}
	string f;
	for(int i=0;i<n;i++){
	    has[f.size()] = i+1;
		f+=s[i];
		f+="`";
	}
	vector<int>sorted = sa(f);
	vector<int>id;
	for(int x:sorted){
		if(has[x])id.push_back(has[x]-1);
		
	}
	vector<string>tmp(n);
	for(int i=0;i<n;i++)tmp[i] = s[id[i]];
	swap(tmp,s);
	vector<vector<pii>>sh(n);
	vector<pii>lab;
	for(int i=0;i<n;i++){
		int k = s[i].size();
		sh[i].resize(k);
		int z1 = 5;
		int z2 = 5;
		pii hb = {0,0};
		for(int j=0;j<k;j++){
			int c = 1;
			if(s[i][k-j-1] == 'c')c=2;
			else if(s[i][k-j-1] == 'g')c=3;
			else if(s[i][k-j-1] == 'u')c=4;
			hb.fi += c * 1LL * z1%MOD1;
			hb.se += c * 1LL * z2%MOD2;
			if(hb.fi>=MOD1)hb.fi-=MOD1;
			if(hb.se>=MOD2)hb.se-=MOD2;
			
			z1 = z1 * 1LL * 5 %MOD1;
			z2 = z2 * 1LL * 5 %MOD2;
			sh[i][j] = hb;
			lab.push_back(hb);
		}
	}
	sort(lab.begin(),lab.end());
	lab.resize(unique(lab.begin(),lab.end()) - lab.begin());
	vector<int>root(n);
	int prev = 0;
	for(int i=0;i<n;i++){
		for(pii x:sh[i]){
			int y = lower_bound(lab.begin(),lab.end(),x) - lab.begin();
			prev = upd(prev,y,0,lab.size()-1);
		}
		root[i] = prev;
	}
	while(m--){
		
		string p,q;
		cin>>p>>q;
		for(char &x:p)x+='a'-'A';
		for(char &x:q)x+='a'-'A';
		reverse(q.begin(),q.end());
		pii suf = make_hash(q);
		int ans = 0;

		int l = 0,r = n-1;
		while(r>=l){
			int mid = (l+r)/2;
			if(cmp(p,s[mid]) <=1 )r = mid-1; //p >= s[mid];
			else l=mid+1;
		}//first guy >= p
		int L = l;
		l = 0,r = n-1;
		while(r>=l){
			int mid = (l+r)/2;
			if(cmp(p,s[mid]) >=1)l= mid+1; //p <= s[mid]
			else r=mid-1;
			
		}
		int R = r;
		if(R>=L){
			int y = lower_bound(lab.begin(),lab.end(),suf) - lab.begin();
			if(lab[y] == suf){
				ans+=query(root[R],0,lab.size()-1,y);
				if(L)ans-=query(root[L-1],0,lab.size()-1,y);
			}
		}
		
		cout<<ans<<'\n';
		
	}
	
	
}

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