oj.uz

Submission #890619

# Submission time Handle Problem Language Result Execution time Memory
890619 2023-12-21T16:16:37 Z iskhakkutbilim Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 907 ms 322900 KB 
#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;
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 235220 KB Output is correct
2 Correct 54 ms 235092 KB Output is correct
3 Correct 53 ms 235148 KB Output is correct
4 Correct 54 ms 235040 KB Output is correct
5 Correct 53 ms 235244 KB Output is correct
6 Correct 54 ms 235088 KB Output is correct
7 Correct 53 ms 235092 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 322900 KB Output is correct
2 Correct 610 ms 322100 KB Output is correct
3 Correct 128 ms 283732 KB Output is correct
4 Correct 129 ms 284280 KB Output is correct
5 Correct 166 ms 291268 KB Output is correct
6 Correct 167 ms 292244 KB Output is correct
7 Correct 335 ms 273080 KB Output is correct
8 Correct 347 ms 298060 KB Output is correct
9 Correct 381 ms 294556 KB Output is correct
10 Correct 225 ms 292688 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 243764 KB Output is correct
2 Correct 91 ms 241524 KB Output is correct
3 Correct 90 ms 242456 KB Output is correct
4 Correct 87 ms 241412 KB Output is correct
5 Correct 82 ms 241160 KB Output is correct
6 Correct 90 ms 242460 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 235220 KB Output is correct
2 Correct 54 ms 235092 KB Output is correct
3 Correct 53 ms 235148 KB Output is correct
4 Correct 54 ms 235040 KB Output is correct
5 Correct 53 ms 235244 KB Output is correct
6 Correct 54 ms 235088 KB Output is correct
7 Correct 53 ms 235092 KB Output is correct
8 Correct 422 ms 322900 KB Output is correct
9 Correct 610 ms 322100 KB Output is correct
10 Correct 128 ms 283732 KB Output is correct
11 Correct 129 ms 284280 KB Output is correct
12 Correct 166 ms 291268 KB Output is correct
13 Correct 167 ms 292244 KB Output is correct
14 Correct 335 ms 273080 KB Output is correct
15 Correct 347 ms 298060 KB Output is correct
16 Correct 381 ms 294556 KB Output is correct
17 Correct 225 ms 292688 KB Output is correct
18 Correct 91 ms 243764 KB Output is correct
19 Correct 91 ms 241524 KB Output is correct
20 Correct 90 ms 242456 KB Output is correct
21 Correct 87 ms 241412 KB Output is correct
22 Correct 82 ms 241160 KB Output is correct
23 Correct 90 ms 242460 KB Output is correct
24 Correct 763 ms 317240 KB Output is correct
25 Correct 699 ms 317536 KB Output is correct
26 Correct 864 ms 316680 KB Output is correct
27 Correct 151 ms 285348 KB Output is correct
28 Correct 907 ms 301504 KB Output is correct
29 Correct 381 ms 270732 KB Output is correct