oj.uz

Submission #839482

# Submission time Handle Problem Language Result Execution time Memory
839482 2023-08-30T06:38:28 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 910 ms 67060 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int NM = 1e5, MOD = 1e9+7, LOG = 17, inf = 1e9+7;

int N, M;
string P[2*NM+5], Q[2*NM+5];
vector <int> pref[2*NM+5], suff[2*NM+5];
int id_pref[2*NM+5], id_suff[2*NM+5], val[2*NM+5], pos[2*NM+5], bit[2*NM+5], ans[NM+5];

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

void process(string &S, vector <int> &f){
	f.resize(S.size()+1);
	f[0] = 0;
	for (int i = 1; i <= S.size(); i++)
		f[i] = ((ll)f[i-1]*4+c(S[i-1]))%MOD;
}

int lcp(vector <int> &f1, vector <int> &f2){
	int l = 1, r = min(f1.size(), f2.size())-1, res = 0;
	while (l <= r){
		int mid = (l+r)/2;
		if (f1[mid] == f2[mid]){
			res = mid;
			l = mid+1;
		}
		else r = mid-1;
	}
	return res;
}

bool cmp_pref(int x, int y){
	int res = lcp(pref[x], pref[y]);
	if (res == min(pref[x], pref[y]).size()-1){
		return pref[x].size() < pref[y].size();
	}
	return c(P[x][res]) < c(P[y][res]);
}

bool cmp_suff(int x, int y){
	int res = lcp(suff[x], suff[y]);
	if (res == min(suff[x], suff[y]).size()-1){
		return suff[x].size() < suff[y].size();
	}
	return c(Q[x][res]) < c(Q[y][res]);
}

void update(int p, int v){
	while (p <= N+M){
		bit[p] += v;
		p += p & (-p);
	}
}

int sum(int p){
	int res = 0;
	while (p > 0){
		res += bit[p];
		p -= p & (-p);
	}
	return res;
}

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 >> P[i];
		Q[i] = P[i];
		reverse(Q[i].begin(), Q[i].end());
		process(P[i], pref[i]);
		process(Q[i], suff[i]);
	}
	for (int i = N+1; i <= N+M; i++){
		cin >> P[i] >> Q[i];
		reverse(Q[i].begin(), Q[i].end());
		process(P[i], pref[i]);
		process(Q[i], suff[i]);
	}
	for (int i = 1; i <= N+M; i++)
		id_pref[i] = id_suff[i] = i;
		
	sort(id_pref+1, id_pref+1+N+M, cmp_pref);
	sort(id_suff+1, id_suff+1+N+M, cmp_suff);
	
	for (int i = 1; i <= N+M; i++)
		val[id_suff[i]] = i;
	for (int i = 1; i <= N+M; i++)
		pos[i] = val[id_pref[i]];
		
	int curL = 1, curR = 0;
	for (int i = 1; i <= N+M; i++){
		if (id_pref[i] <= N) continue;
		int k = pref[id_pref[i]].size()-1, L = i, R = i;
		int l = 1, r = i-1;
		while (l <= r){
			int mid = (l+r)/2;
			if (lcp(pref[id_pref[mid]], pref[id_pref[i]]) >= k){
				L = mid;
				r = mid-1;
			}
			else l = mid+1;
		}
		l = i+1, r = N+M;
		while (l <= r){
			int mid = (l+r)/2;
			if (lcp(pref[id_pref[i]], pref[id_pref[mid]]) >= k){
				R = mid;
				l = mid+1;
			}
			else r = mid-1;
		}
		while (curL > L){
			curL--;
			if (id_pref[curL] <= N) update(pos[curL], 1);
		}
		while (curR < R){
			curR++;
			if (id_pref[curR] <= N) update(pos[curR], 1);
		}
		while (curL < L){
			if (id_pref[curL] <= N) update(pos[curL], -1);
			curL++;
		}
		while (curR > R){
			if (id_pref[curR] <= N) update(pos[curR], -1);
			curR--;
		}
		
		k = suff[id_suff[pos[i]]].size()-1;
		int resl = pos[i], resr = pos[i];
		l = 1, r = pos[i]-1;
		while (l <= r){
			int mid = (l+r)/2;
			if (lcp(suff[id_suff[mid]], suff[id_suff[pos[i]]]) >= k){
				resl = mid;
				r = mid-1;
			}
			else l = mid+1;
		}
		l = pos[i]+1, r = N+M;
		while (l <= r){
			int mid = (l+r)/2;
			if (lcp(suff[id_suff[pos[i]]], suff[id_suff[mid]]) >= k){
				resr = mid;
				l = mid+1;
			}
			else r = mid-1;
		}
		ans[id_pref[i]-N] = sum(resr)-sum(resl-1);
	}
	for (int i = 1; i <= M; i++)
		cout << ans[i] << '\n';
	return 0;
}

Compilation message

selling_rna.cpp: In function 'void process(std::string&, std::vector<int>&)':
selling_rna.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for (int i = 1; i <= S.size(); i++)
      |                  ~~^~~~~~~~~~~
selling_rna.cpp: In function 'bool cmp_pref(int, int)':
selling_rna.cpp:42:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  if (res == min(pref[x], pref[y]).size()-1){
      |      ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'bool cmp_suff(int, int)':
selling_rna.cpp:50:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  if (res == min(suff[x], suff[y]).size()-1){
      |      ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22228 KB Output is correct
2 Correct 10 ms 22228 KB Output is correct
3 Correct 9 ms 22284 KB Output is correct
4 Correct 10 ms 22284 KB Output is correct
5 Correct 10 ms 22228 KB Output is correct
6 Correct 10 ms 22288 KB Output is correct
7 Correct 9 ms 22228 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 52048 KB Output is correct
2 Correct 152 ms 52588 KB Output is correct
3 Correct 148 ms 52428 KB Output is correct
4 Correct 151 ms 52516 KB Output is correct
5 Correct 82 ms 41404 KB Output is correct
6 Correct 85 ms 41608 KB Output is correct
7 Correct 155 ms 57116 KB Output is correct
8 Correct 181 ms 62200 KB Output is correct
9 Correct 188 ms 62236 KB Output is correct
10 Correct 134 ms 49908 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 30868 KB Output is correct
2 Correct 97 ms 27800 KB Output is correct
3 Correct 116 ms 29272 KB Output is correct
4 Correct 83 ms 27964 KB Output is correct
5 Correct 89 ms 27744 KB Output is correct
6 Correct 116 ms 29336 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22228 KB Output is correct
2 Correct 10 ms 22228 KB Output is correct
3 Correct 9 ms 22284 KB Output is correct
4 Correct 10 ms 22284 KB Output is correct
5 Correct 10 ms 22228 KB Output is correct
6 Correct 10 ms 22288 KB Output is correct
7 Correct 9 ms 22228 KB Output is correct
8 Correct 135 ms 52048 KB Output is correct
9 Correct 152 ms 52588 KB Output is correct
10 Correct 148 ms 52428 KB Output is correct
11 Correct 151 ms 52516 KB Output is correct
12 Correct 82 ms 41404 KB Output is correct
13 Correct 85 ms 41608 KB Output is correct
14 Correct 155 ms 57116 KB Output is correct
15 Correct 181 ms 62200 KB Output is correct
16 Correct 188 ms 62236 KB Output is correct
17 Correct 134 ms 49908 KB Output is correct
18 Correct 118 ms 30868 KB Output is correct
19 Correct 97 ms 27800 KB Output is correct
20 Correct 116 ms 29272 KB Output is correct
21 Correct 83 ms 27964 KB Output is correct
22 Correct 89 ms 27744 KB Output is correct
23 Correct 116 ms 29336 KB Output is correct
24 Correct 243 ms 54232 KB Output is correct
25 Correct 307 ms 56780 KB Output is correct
26 Correct 194 ms 53312 KB Output is correct
27 Correct 251 ms 54208 KB Output is correct
28 Correct 910 ms 67060 KB Output is correct
29 Correct 798 ms 52000 KB Output is correct