제출 #890619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
890619		iskhakkutbilim	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	907 ms	322900 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 2000000;
const int P = 31;
const int mod = 1e9 + 9;
int pw[N+10];
int n, m;
vector<string> a;
vector<vector<int> > Hashings;
vector<int> turn_hash(string &s){
	vector<int> h;
	h.push_back(s[0]);
	for(int i = 1;i < (int)s.size(); i++){
		int pref = ((h.back() * P) % mod + s[i]) % mod;
		h.push_back(pref);
	}
	return h;
}
int into(char ch){
	if(ch == 'A') return 0;
	if(ch == 'C') return 1;
	if(ch == 'G') return 2;
	return 3;
}

int vert = 1;


struct node{
	vector<int> idx = {};
	int nxt[4] = {-1, -1, -1, -1};
};
node trie[N * 2];

void add(string &s, int pos){
	int cur = 0;
	for(int i = 0;i < s.size(); i++){
		int k = into(s[i]);
		if(trie[cur].nxt[k] == -1) trie[cur].nxt[k] = vert++;
		cur = trie[cur].nxt[k];
		trie[cur].idx.push_back(pos);
	}
}

int count(string &s, int l, int r){
	int cur = 0;
	for(int i = 0;i < (int)s.size(); i++){
		int k = into(s[i]);
		cur = trie[cur].nxt[k];
		if(cur == -1) return 0;
	}
	
	vector<int> &v = trie[cur].idx;
	int it = lower_bound(all(v), l) - v.begin();
	int it1 = upper_bound(all(v), r) - v.begin();
	return it1 - it;
}


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	a.resize(n);
	pw[0] = 1;
	for(int i = 1;i <= N; i++){
		pw[i] = (pw[i-1] * P) % mod;
	}
	vector< vector<int> > vece;
	for(auto &e : a){
		cin >> e;
		vece.push_back(turn_hash(e));
	}
	vector<int> p;
	for(int i = 0;i < n; i++) p.push_back(i);
	auto get=[&](vector<int> &cur, int l, int r){
		if(l == 0) return cur[r];
		int all =  (cur[r] - (cur[l-1] * pw[r-l+1]) % mod);
		all = ((all % mod) + mod) % mod;
		return all;
	};
	sort(all(p), [&](int i, int j){
		
		if(a[i][0] != a[j][0]){
			return into(a[i][0]) < into(a[j][0]);
		} 
		int low = 0, high = min(a[i].size(), a[j].size());
		while(high-low > 1){
			int mid = (low + high) / 2;
			if(get(vece[i], 0, mid) == get(vece[j], 0, mid)){
				low = mid;
			}else{
				high = mid;
			}
		}
		low++;
		if(low >= (int)a[i].size() || low >= a[j].size()){
			return a[i].size() < a[j].size();
		}
		return into(a[i][low]) < into(a[j][low]);
	});
	vector<string> aa = a;
	a.clear();
	for(int i : p){
		a.push_back(aa[i]);
	}
	for(int i = 0;i < a.size(); i++){
		string t = a[i];
	//	cout << a[i] << "\n";
		reverse(all(t));
		add(t, i);
	}
	//cout << '\n' << '\n';
	
	while(m--){
		string p, q; cin >> p >> q;
		int l = 0, r = n-1;
		for(int i = 0;i < p.size(); i++){
			int lo = l-1, ro = r+1;
			while(lo + 1 < ro){
				int mid = (lo + ro) >> 1;
				if(i + 1 <= a[mid].size() && a[mid][i] > p[i]){
					ro = mid;
				}else lo = mid;
			}
			int ss = ro-1;
			lo = l-1, ro = r+1;
			while(lo + 1 < ro){
				int mid = (lo + ro) >> 1;
				if(i + 1 > a[mid].size() || a[mid][i] < p[i]) lo = mid;
				else ro = mid;
			}
			l = lo+1, r = ss;
			if(l > r) break;
		}
		reverse(all(q));
		//cout << p << " = " << l << ' ' << r << '\n';
		cout << count(q, l, r) << '\n';
		
	}
	return 0;
}

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

selling_rna.cpp: In function 'void add(std::string&, long long int)':
selling_rna.cpp:41:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i = 0;i < s.size(); i++){
      |                ~~^~~~~~~~~~
selling_rna.cpp: In lambda function:
selling_rna.cpp:101:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   if(low >= (int)a[i].size() || low >= a[j].size()){
      |                                 ~~~~^~~~~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:111:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for(int i = 0;i < a.size(); i++){
      |                ~~^~~~~~~~~~
selling_rna.cpp:122:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |   for(int i = 0;i < p.size(); i++){
      |                 ~~^~~~~~~~~~
selling_rna.cpp:126:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     if(i + 1 <= a[mid].size() && a[mid][i] > p[i]){
      |        ~~~~~~^~~~~~~~~~~~~~~~
selling_rna.cpp:134:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     if(i + 1 > a[mid].size() || a[mid][i] < p[i]) lo = mid;
      |        ~~~~~~^~~~~~~~~~~~~~~

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