제출 #51148

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51148		spencercompton	Selling RNA Strands (JOI16_selling_rna)	C++17	10 / 100	1554 ms	62508 KiB

selling_rna

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

int tr1[4][100001];
int tr2[4][100001];
vector<int> end1[100001];
vector<int> end2[100001];
int sum1[100001];
int sum2[100001];
int p1 = 1;
int p2 = 1;
int cpos = -1;
vector<int> cs;
int cind = -1;
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<=100000; 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;
	//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.push_back(Query(ra.first,rb.first,i,true));
		q.push_back(Query(ra.first,rb.first+rb.second,i,false));
		q.push_back(Query(ra.first+ra.second,rb.first,i,false));
		q.push_back(Query(ra.first+ra.second,rb.first+rb.second,i,true));
	}
	sort(q.begin(),q.end());
	for(int i = 0; i<q.size(); i++){
		int now = 0;
		for(int j = 0; j<n; j++){
			if(fir[j]<=q[i].tim && sec[j]<=q[i].x){
				now++;
			}
		}
		if(q[i].add){
			ans[q[i].id] += now;
		}
		else{
			ans[q[i].id] -= now;
		}
	}
	for(int i = 0; i<m; i++){
		cout << ans[i] << endl;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'void add1(int)':
selling_rna.cpp:31: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:43: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:54: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:72: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:92: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:102: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:141:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<s.length(); j++){
                  ~^~~~~~~~~~~
selling_rna.cpp:187:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<a.length(); j++){
                  ~^~~~~~~~~~~
selling_rna.cpp:205:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<q.size(); i++){
                 ~^~~~~~~~~

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