Submission #51150

#	Time	Username	Problem	Language	Result	Execution time	Memory
51150		spencercompton	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	680 ms	242616 KiB

selling_rna

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

int tr1[4][2000001];
int tr2[4][2000001];
vector<int> end1[2000001];
vector<int> end2[2000001];
int sum1[2000001];
int sum2[2000001];
int p1 = 1;
int p2 = 1;
int cpos = -1;
vector<int> cs;
int cind = -1;
class Fenwick{
	public:
		vector<int> ar;
		int n;
		Fenwick(int a){
			n = a+2;
			ar.resize(n);
		}
		void add(int ind, int v){
			for(;ind<n; ind += (ind&(-ind))){
				ar[ind] += v;
			}
		}
		int sum(int ind){
			if(ind==0){
				return 0;
			}
			int ret = 0;
			for(;ind>0; ind -= (ind&(-ind))){
				ret += ar[ind];
			}
			return ret;
		}
};
class Query{
	public:
		int tim, x, id;
		bool add;
		Query(int a, int b, int d, bool c){
			tim = a;
			x = b;
			id = d;
			add = c;
		}
		bool operator<(const Query &o) const{
			return tim<o.tim;
		}
};
void add1(int now){
	sum1[now]++;
	if(cpos==cs.size()){
		end1[now].push_back(cind);
		return;
	}
	if(tr1[cs[cpos]][now]==-1){
		tr1[cs[cpos]][now] = p1++;
	}
	cpos++;
	add1(tr1[cs[cpos-1]][now]);
}
void add2(int now){
	sum2[now]++;
	if(cpos==cs.size()){
		end2[now].push_back(cind);
		return;
	}
	if(tr2[cs[cpos]][now]==-1){
		tr2[cs[cpos]][now] = p2++;
	}
	cpos++;
	add2(tr2[cs[cpos-1]][now]);
}
pair<int, int> r1(int now){
	if(cpos==cs.size()){
		return make_pair(0,sum1[now]);
	}
	if(tr1[cs[cpos]][now]==-1){
		return make_pair(0,0);
	}
	int bef = end1[now].size();
	for(int i = 0; i<cs[cpos]; i++){
		if(tr1[i][now]!=-1){
			bef += sum1[tr1[i][now]];
		}
	}
	cpos++;
	pair<int, int> ret = r1(tr1[cs[cpos-1]][now]);
	ret.first += bef;
	return ret;
}
pair<int, int> r2(int now){
	if(cpos==cs.size()){
		return make_pair(0,sum2[now]);
	}
	if(tr2[cs[cpos]][now]==-1){
		return make_pair(0,0);
	}
	int bef = end2[now].size();
	for(int i = 0; i<cs[cpos]; i++){
		if(tr2[i][now]!=-1){
			bef += sum2[tr2[i][now]];
		}
	}
	cpos++;
	pair<int, int> ret = r2(tr2[cs[cpos-1]][now]);
	ret.first += bef;
	return ret;
}
vector<int> l1;
vector<int> l2;
void s1(int now){
	for(int i = 0; i<end1[now].size(); i++){
		l1.push_back(end1[now][i]);
	}
	for(int i = 0; i<4; i++){
		if(tr1[i][now]!=-1){
			s1(tr1[i][now]);
		}
	}
}
void s2(int now){
	for(int i = 0; i<end2[now].size(); i++){
		l2.push_back(end2[now][i]);
	}
	for(int i = 0; i<4; i++){
		if(tr2[i][now]!=-1){
			s2(tr2[i][now]);
		}
	}
}
int ff(char c){
	if(c=='A'){
		return 0;
	}
	if(c=='C'){
		return 1;
	}
	if(c=='G'){
		return 2;
	}
	return 3;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	for(int i = 0; i<4; i++){
		for(int j = 0; j<=2000000; j++){
			tr1[i][j] = -1;
			tr2[i][j] = -1;
			sum1[j] = 0;
			sum2[j] = 0;
		}
	}
	int n, m;
	cin >> n >> m;
	vector<int> f[n];
	vector<int> b[n];
	for(int i = 0; i<n; i++){
		string s;
		cin >> s;
		for(int j = 0; j<s.length(); j++){
			f[i].push_back(ff(s[j]));
		}
		for(int j = s.length()-1; j>=0; j--){
			b[i].push_back(ff(s[j]));
		}
	}
	for(int i = 0; i<n; i++){
		cs = f[i];
		cpos = 0;
		cind = i;
		add1(0);
		cpos = 0;
		cs = b[i];
		add2(0);
	}
	s1(0);
	s2(0);
	// for(int i = 0; i<n; i++){
	// 	cout << l1[i] << endl;
	// }
	// for(int i = 0; i<n; i++){
	// 	cout << l2[i] << endl;
	// }
	int fir[n];
	int sec[n];
	for(int i = 0; i<n; i++){
		fir[l1[i]] = i+1;
		sec[l2[i]] = i+1;
	}
	vector<pair<int, int> > li;
	for(int i = 0; i<n; i++){
		li.push_back(make_pair(fir[i],sec[i]));
	}
	sort(li.begin(),li.end());
	int ans[m];
	for(int i = 0; i<m; i++){
		ans[i] = 0;
	}
	vector<Query> q[n+1];
	//tim, x, id, add
	for(int i = 0; i<m; i++){
		string a, bb;
		cin >> a >> bb;
		vector<int> f;
		vector<int> b;
		for(int j = 0; j<a.length(); j++){
			f.push_back(ff(a[j]));
		}
		for(int j = bb.length()-1; j>=0; j--){
			b.push_back(ff(bb[j]));
		}
		cs = f;
		cpos = 0;
		pair<int, int> ra = r1(0);
		cs = b;
		cpos = 0;
		pair<int, int> rb = r2(0);
		q[ra.first].push_back(Query(ra.first,rb.first,i,true));
		q[ra.first].push_back(Query(ra.first,rb.first+rb.second,i,false));
		q[ra.first+ra.second].push_back(Query(ra.first+ra.second,rb.first,i,false));
		q[ra.first+ra.second].push_back(Query(ra.first+ra.second,rb.first+rb.second,i,true));
	}
	Fenwick fen = Fenwick(n+2);
	for(int i = 0; i<=n; i++){
		for(int j = 0; j<q[i].size(); j++){
			int now = fen.sum(q[i][j].x);
			if(q[i][j].add){
				ans[q[i][j].id] += now;
			}
			else{
				ans[q[i][j].id] -= now;
			}
		}
		if(i<n){
			fen.add(li[i].second,1);
		}
	}
	for(int i = 0; i<m; i++){
		cout << ans[i] << endl;
	}
}

Compilation message (stderr)

selling_rna.cpp: In function 'void add1(int)':
selling_rna.cpp:55:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cpos==cs.size()){
     ~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'void add2(int)':
selling_rna.cpp:67:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cpos==cs.size()){
     ~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'std::pair<int, int> r1(int)':
selling_rna.cpp:78:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cpos==cs.size()){
     ~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'std::pair<int, int> r2(int)':
selling_rna.cpp:96:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cpos==cs.size()){
     ~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'void s1(int)':
selling_rna.cpp:116:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<end1[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void s2(int)':
selling_rna.cpp:126:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<end2[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:165:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<s.length(); j++){
                  ~^~~~~~~~~~~
selling_rna.cpp:211:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<a.length(); j++){
                  ~^~~~~~~~~~~
selling_rna.cpp:230:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<q[i].size(); j++){
                  ~^~~~~~~~~~~~

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