제출 #585999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585999		Ace	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	1101 ms	249080 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
 
typedef pair<int,int> pii;
typedef pair<string,int> psi;
const int N = 1e5;
const int MAXN = 2e6;

struct trie{
	int nxt[4];
	vector<int> isi;
};

trie dep[MAXN+5], bel[MAXN+5];
int cntDep = 0;
int cntBel = 0;

int getNum(char x){
	if(x == 'A') return 0;
	if(x == 'G') return 1;
	if(x == 'C') return 2;
	return 3;
}

void insert(int node, string &s, int idx, int id, trie *t, int &cnt){
	t[node].isi.push_back(idx);
	if(id == s.size()) return;
	int cur = getNum(s[id]);
	if(t[node].nxt[cur] == -1) {
		cnt++;
		memset(t[cnt].nxt,-1,sizeof(t[cnt].nxt));
		t[node].nxt[cur] = cnt;
	}
	insert(t[node].nxt[cur], s, idx, id+1, t, cnt);
}

vector<int> query(int node, string &s, int id, trie *t){
	if(node == -1) return vector<int>();
	if(id == s.size()) {
		return t[node].isi;
	}
	int cur = getNum(s[id]);
	return query(t[node].nxt[cur], s, id+1, t);
}

string li[N+5];
 
int n,m;
 
string pre[N+5], suf[N+5];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> li[i];
	}
	
	sort(li+1,li+n+1);
	memset(dep[0].nxt,-1,sizeof(dep[0].nxt));
	memset(bel[0].nxt,-1,sizeof(bel[0].nxt));
	
	for(int i=1;i<=n;i++){
		insert(0, li[i], i, 0, dep, cntDep);
		string rev = li[i];
		reverse(rev.begin(), rev.end());
		insert(0, rev, i, 0, bel, cntBel);
	}
	
	
	for(int i=1;i<=m;i++){
		cin >> pre[i] >> suf[i];
		reverse(suf[i].begin(), suf[i].end());
		vector<int> retPre = query(0, pre[i], 0, dep);
		if(retPre.size() == 0) {
			cout << "0\n";
			continue;
		}
		vector<int> retSuf = query(0, suf[i], 0, bel);
		int l = retPre[0];
		int r = retPre.back();
		int idl = lower_bound(retSuf.begin(), retSuf.end(), l) - retSuf.begin();
		int idr = upper_bound(retSuf.begin(), retSuf.end(), r) - retSuf.begin();
		cout << idr-idl << "\n";
	}
	
	
	return 0;
}

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

selling_rna.cpp: In function 'void insert(int, std::string&, int, int, trie*, int&)':
selling_rna.cpp:27:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  if(id == s.size()) return;
      |     ~~~^~~~~~~~~~~
selling_rna.cpp: In function 'std::vector<int> query(int, std::string&, int, trie*)':
selling_rna.cpp:39:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  if(id == s.size()) {
      |     ~~~^~~~~~~~~~~

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