Submission #839479

#	Time	Username	Problem	Language	Result	Execution time	Memory
839479		daoquanglinh2007	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	668 ms	94820 KiB

selling_rna

#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];
int lcp_pref[2*NM+5], lcp_suff[2*NM+5];
int sp_pref[LOG+5][2*NM+5], sp_suff[LOG+5][2*NM+5];
int val[2*NM+5], pos[2*NM+5], bit[2*NM+5];
int ans[NM+5];

int c(char ch){
	if (ch == 'A') return 0;
	if (ch == 'C') return 1;
	if (ch == 'G') 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 build_sparse_table(){
	for (int i = 1; i < N+M; i++){
		sp_pref[0][i] = lcp_pref[i];
		sp_suff[0][i] = lcp_suff[i];
	}
	for (int i = 1; i <= LOG; i++)
		for (int j = 1; j+(1<<i)-1 < N+M; j++){
			sp_pref[i][j] = min(sp_pref[i-1][j], sp_pref[i-1][j+(1<<(i-1))]);
			sp_suff[i][j] = min(sp_suff[i-1][j], sp_suff[i-1][j+(1<<(i-1))]);
		}
}

int get_lcp_pref(int l, int r){
	if (l > r) return +inf;
	if (l == r) return pref[l].size()-1;
	r--;
	int i = __lg(r-l+1);
	return min(sp_pref[i][l], sp_pref[i][r-(1<<i)+1]);
}

int get_lcp_suff(int l, int r){
	if (l > r) return +inf;
	if (l == r) return suff[l].size()-1;
	r--;
	int i = __lg(r-l+1);
	return min(sp_suff[i][l], sp_suff[i][r-(1<<i)+1]);
}

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++){
		lcp_pref[i] = lcp(pref[id_pref[i]], pref[id_pref[i+1]]);
		lcp_suff[i] = lcp(suff[id_suff[i]], suff[id_suff[i+1]]);
	}
	build_sparse_table();
	
	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 (get_lcp_pref(mid, 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 (get_lcp_pref(i, 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 (get_lcp_suff(mid, 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 (get_lcp_suff(pos[i], 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 (stderr)

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

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