Submission #963883

#	Time	Username	Problem	Language	Result	Execution time	Memory
963883		LCJLY	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	291 ms	266980 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;	
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
typedef pair<int,pii>pi2;
 
struct trie{	
	trie *next[4];
	int in=0;
	int out=0;
	trie(){
		next[0]=next[1]=next[2]=next[3]=NULL;
	}	
};
 
auto rt=new trie();
auto rev=new trie();
 
int f(char a){
	if(a=='A') return 0;
	else if(a=='C') return 1;
	else if(a=='G') return 2;
	else return 3;
}
 
int ptr=0;
 
void dfs(trie*cur){
	cur->in=++ptr;
	for(int x=0;x<4;x++){
		if(cur->next[x]!=NULL){
			dfs(cur->next[x]);
		}
	}
	cur->out=ptr;
}
 
int fw[200005];
 
void upd(int x, int y){	
	while(x<200005){
		fw[x]+=y;
		x+=x&(-x);
	}	
}
 
int sum(int x){
	int counter=0;
	while(x>0){
		counter+=fw[x];
		x-=x&(-x);
	}
	return counter;
}
 
void rangeUpd(int x, int y, int c){		
	upd(x,c);
	upd(x+1,-c);
}
 
int query(int x, int y){
	return sum(y)-sum(x-1);
}
 
int ans[100005];
vector<array<int,4>>storage[200005];
 
void solve(){
	int n,m;
	cin >> n >> m;
	string arr[n];
	for(int x=0;x<n;x++){
		cin >> arr[x];
		//front
		auto cur=rt;
		for(int y=0;y<(int)arr[x].length();y++){
			int hold=f(arr[x][y]);
			if(cur->next[hold]==NULL) cur->next[hold]=new trie();
			cur=cur->next[hold];
		}
		
		//back
		string s=arr[x];
		reverse(s.begin(),s.end());
		cur=rev;
		for(int y=0;y<(int)s.length();y++){
			int hold=f(s[y]);
			if(cur->next[hold]==NULL) cur->next[hold]=new trie();
			cur=cur->next[hold];
		}
	}
	
	dfs(rt);
	ptr=0;
	dfs(rev);
	
	vector<int>dis;
	
	vector<pii>v;
	for(int x=0;x<n;x++){
		string s=arr[x];
		reverse(s.begin(),s.end());
		int sz=s.length();
		
		auto cur=rt;
		auto cur2=rev;
		for(int y=0;y<sz;y++){
			int hold=f(arr[x][y]);
			int hold2=f(s[y]);
			cur=cur->next[hold];
			cur2=cur2->next[hold2];
		}
		
		v.push_back({cur->in,cur2->in});
		dis.push_back(cur2->in);
	}
	
	string temp,temp2;
	for(int x=0;x<m;x++){
		cin >> temp >> temp2;
		//front
		auto cur=rt;
		int sz=temp.size();
		bool amos=true;
		for(int y=0;y<sz;y++){
			int hold=f(temp[y]);
			if(cur->next[hold]==NULL){
				amos=false;
				break;
			}
			cur=cur->next[hold];
		}
		
		reverse(temp2.begin(),temp2.end());
		auto cur2=rev;
		sz=temp2.size();
		for(int y=0;y<sz;y++){
			int hold=f(temp2[y]);
			if(cur2->next[hold]==NULL){
				amos=false;
				break;
			}
			cur2=cur2->next[hold];
		}
		
		if(!amos) continue;
		else{
			storage[cur->in-1].push_back({cur2->in,cur2->out,x,-1});
			storage[cur->out].push_back({cur2->in,cur2->out,x,1});
			dis.push_back(cur2->in);
			dis.push_back(cur2->out);
		}
	}
	
	//l r index sign
	
	sort(v.begin(),v.end());
	sort(dis.begin(),dis.end());
	dis.resize(unique(dis.begin(),dis.end())-dis.begin());
	int swp=0;
	for(int x=0;x<150005;x++){
		while(swp<(int)v.size()&&v[swp].first<=x){
			v[swp].second=lower_bound(dis.begin(),dis.end(),v[swp].second)-dis.begin()+1;
			upd(v[swp].second,1);
			swp++;
		}
		
		for(auto it:storage[x]){
			int l=lower_bound(dis.begin(),dis.end(),it[0])-dis.begin()+1;
			int r=lower_bound(dis.begin(),dis.end(),it[1])-dis.begin()+1;
			ans[it[2]]+=(query(l,r)*it[3]);
		}
	}
	
	for(int x=0;x<m;x++){
		cout << ans[x] << "\n";
	}
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

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