Submission #87416

#	Time	Username	Problem	Language	Result	Execution time	Memory
87416		KLPP	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	1280 ms	599376 KiB

selling_rna

#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;
#define MOD 1000000007
#define BASE 257
typedef long long int lld;
typedef pair<int,int> pii;
class FT{
	int FT[2000000];
	int N;
	public:
	void init(int n){
		N=n;
		for(int i=0;i<=N;i++)FT[i]=0;
	}
	void upd(int pos){
		for(int i=pos;i<=N;i+=i&(-i)){
			FT[i]++;
		}
	}
	int query(int pos){
		int ans=0;
		for(int i=pos;i>0;i-=i&(-i)){
			ans+=FT[i];
		}return ans;
	}
};
struct Trie{
	struct Trie *child[26];
	vector<int> end;
};
void insert(Trie *T,string s, int index){
	Trie *S=T;
	for(int i=0;i<s.length();i++){
		int u=s[i]-'A';
		if(!S->child[u]){
			S->child[u]=new Trie();
			for(int j=0;j<26;j++)S->child[u]->child[j]=NULL;
		}
		S=S->child[u];
	}
	S->end.push_back(index);
}
pair<int,int> Query1[1000000];
vector<int> EulerTour1;
pair<int,int> Query2[1000000];
vector<int> EulerTour2;
void DFS1(Trie *T){
	sort(T->end.begin(),T->end.end());
	for(int i=0;i<T->end.size();i++){
		if(T->end[i]<=0){
			Query1[-T->end[i]].first=EulerTour1.size();
		}else EulerTour1.push_back(T->end[i]-1);
		//cout<<T->end[i]<<" ";
	}
	//cout<<endl;
	for(int i=0;i<26;i++){
		if(T->child[i]){
			DFS1(T->child[i]);
		}
	}
	for(int i=0;i<T->end.size();i++){
		if(T->end[i]<=0){
			Query1[-T->end[i]].second=EulerTour1.size();
		}
		//cout<<T->end[i]<<" ";
	}
}
void DFS2(Trie *T){
	sort(T->end.begin(),T->end.end());
	for(int i=0;i<T->end.size();i++){
		if(T->end[i]<=0){
			Query2[-T->end[i]].first=EulerTour2.size();
		}else EulerTour2.push_back(T->end[i]-1);
		//cout<<T->end[i]<<" ";
	}
	//cout<<endl;
	for(int i=0;i<26;i++){
		if(T->child[i]){
			DFS2(T->child[i]);
		}
	}
	for(int i=0;i<T->end.size();i++){
		if(T->end[i]<=0){
			Query2[-T->end[i]].second=EulerTour2.size();
		}
		//cout<<T->end[i]<<" ";
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	string arr[n];
	Trie *T=new Trie();
	for(int i=0;i<n;i++){
		cin>>arr[i];
		insert(T,arr[i],i+1);
	}
	string Queries1[m];
	string Queries2[m];
	for(int i=0;i<m;i++){
		cin>>Queries1[i]>>Queries2[i];
		insert(T,Queries1[i],-i);
	}
	DFS1(T);
	/*for(int i=0;i<n;i++){
		cout<<EulerTour1[i]<<endl;
	}
	for(int i=0;i<m;i++){
		cout<<Query1[i].first<<" "<<Query1[i].second<<endl;
	}*/
	T=new Trie();
	for(int i=0;i<n;i++){
		reverse(arr[i].begin(),arr[i].end());
		insert(T,arr[i],i+1);
	}
	for(int i=0;i<m;i++){
		reverse(Queries2[i].begin(),Queries2[i].end());
		insert(T,Queries2[i],-i);
	}
	DFS2(T);
	/*for(int i=0;i<m;i++){
		cout<<Query2[i].first<<" "<<Query2[i].second<<endl;
	}*/
	pair<int,int> ET[n];
	for(int i=0;i<n;i++){
		ET[EulerTour1[i]].first=i;
		ET[EulerTour2[i]].second=i;
	}sort(ET,ET+n);
	int answer[4*m];
	vector<pair<pii,int> >Queries;
	for(int i=0;i<m;i++){
		Queries.push_back(pair<pii,int>(pii(Query1[i].first,Query2[i].first),4*i));
		Queries.push_back(pair<pii,int>(pii(Query1[i].first,Query2[i].second),4*i+1));
		Queries.push_back(pair<pii,int>(pii(Query1[i].second,Query2[i].first),4*i+2));
		Queries.push_back(pair<pii,int>(pii(Query1[i].second,Query2[i].second),4*i+3));
	}
	sort(Queries.begin(),Queries.end());
	int pnt=0;
	FT *F=new FT();
	F->init(n);
	for(int i=0;i<4*m;i++){
		while(pnt<Queries[i].first.first){
			pnt++;
			F->upd(ET[pnt-1].second+1);
		}
		answer[Queries[i].second]=F->query(Queries[i].first.second);
	}
	for(int i=0;i<m;i++){
		cout<<answer[4*i]+answer[4*i+3]-answer[4*i+1]-answer[4*i+2]<<endl;
	}
	
	//cout<<'G'-'A'<<endl;
	
	
	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'void insert(Trie*, std::__cxx11::string, int)':
selling_rna.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.length();i++){
              ~^~~~~~~~~~~
selling_rna.cpp: In function 'void DFS1(Trie*)':
selling_rna.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T->end.size();i++){
              ~^~~~~~~~~~~~~~
selling_rna.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T->end.size();i++){
              ~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'void DFS2(Trie*)':
selling_rna.cpp:73:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T->end.size();i++){
              ~^~~~~~~~~~~~~~
selling_rna.cpp:85:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T->end.size();i++){
              ~^~~~~~~~~~~~~~

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