oj.uz

Submission #839484

# Submission time Handle Problem Language Result Execution time Memory
839484 2023-08-30T06:43:36 Z daoquanglinh2007 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 728 ms 67076 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define sz(S) (int)(S).size()

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(sz(S)+1);
	f[0] = 0;
	for (int i = 1; i <= sz(S); 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(sz(f1), sz(f2))-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(sz(pref[x]), sz(pref[y]))-1){
		return sz(pref[x]) < sz(pref[y]);
	}
	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(sz(suff[x]), sz(suff[y]))-1){
		return sz(suff[x]) < sz(suff[y]);
	}
	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 = sz(pref[id_pref[i]])-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 = sz(suff[id_suff[pos[i]]])-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;
}

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 10 ms 22228 KB Output is correct
4 Correct 10 ms 22228 KB Output is correct
5 Correct 11 ms 22228 KB Output is correct
6 Correct 10 ms 22228 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 78 ms 52148 KB Output is correct
2 Correct 94 ms 52512 KB Output is correct
3 Correct 87 ms 52428 KB Output is correct
4 Correct 95 ms 52536 KB Output is correct
5 Correct 79 ms 41472 KB Output is correct
6 Correct 80 ms 41556 KB Output is correct
7 Correct 96 ms 57176 KB Output is correct
8 Correct 128 ms 62228 KB Output is correct
9 Correct 123 ms 62156 KB Output is correct
10 Correct 82 ms 49812 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 30904 KB Output is correct
2 Correct 81 ms 27724 KB Output is correct
3 Correct 110 ms 29260 KB Output is correct
4 Correct 74 ms 27928 KB Output is correct
5 Correct 83 ms 27752 KB Output is correct
6 Correct 112 ms 29388 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 10 ms 22228 KB Output is correct
4 Correct 10 ms 22228 KB Output is correct
5 Correct 11 ms 22228 KB Output is correct
6 Correct 10 ms 22228 KB Output is correct
7 Correct 9 ms 22228 KB Output is correct
8 Correct 78 ms 52148 KB Output is correct
9 Correct 94 ms 52512 KB Output is correct
10 Correct 87 ms 52428 KB Output is correct
11 Correct 95 ms 52536 KB Output is correct
12 Correct 79 ms 41472 KB Output is correct
13 Correct 80 ms 41556 KB Output is correct
14 Correct 96 ms 57176 KB Output is correct
15 Correct 128 ms 62228 KB Output is correct
16 Correct 123 ms 62156 KB Output is correct
17 Correct 82 ms 49812 KB Output is correct
18 Correct 104 ms 30904 KB Output is correct
19 Correct 81 ms 27724 KB Output is correct
20 Correct 110 ms 29260 KB Output is correct
21 Correct 74 ms 27928 KB Output is correct
22 Correct 83 ms 27752 KB Output is correct
23 Correct 112 ms 29388 KB Output is correct
24 Correct 149 ms 54272 KB Output is correct
25 Correct 244 ms 56776 KB Output is correct
26 Correct 118 ms 53368 KB Output is correct
27 Correct 160 ms 54196 KB Output is correct
28 Correct 728 ms 67076 KB Output is correct
29 Correct 619 ms 52072 KB Output is correct