Submission #378114

#	Time	Username	Problem	Language	Result	Execution time	Memory
378114		reymontada61	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	942 ms	35924 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

int n, q;
const int MXN = 100005;
string arr[MXN];
vector<pair<string, int>> proc;

string pre, suf;
bool usep;

bool after(int x) {
	if (usep) {
		for (int i=0; i<min(pre.size(), arr[x].size()); i++) {
			if (pre[i] < arr[x][i]) return true;
			if (pre[i] > arr[x][i]) return false;
		}
		return arr[x].size() >= pre.size();
	}
	else {
		for (int i=0; i<min(suf.size(), proc[x].first.size()); i++) {
			if (suf[i] < proc[x].first[i]) return true;
			if (suf[i] > proc[x].first[i]) return false;
		}
		return proc[x].first.size() >= suf.size();
	}
}

int first() {
	if (!after(n)) return n + 1;
	int low = 1;
	int high = n;
	while (low < high) {
		int mid = (low + high) / 2;
		if (after(mid)) {
			high = mid;
		}
		else {
			low = mid + 1;
		}
	}
	return low;
}

vector<int> vec[MXN*4];

void build(int ind, int l, int r) {
	for (int x=l; x<=r; x++) {
		vec[ind].push_back(proc[x].second);
	}
	sort(vec[ind].begin(), vec[ind].end());
	if (l == r) {
		return;
	}
	int m = (l + r) / 2;
	build(ind*2, l, m);
	build(ind*2+1, m+1, r);
}

int LB, RB;

int query(int ind, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) {
		return upper_bound(vec[ind].begin(), vec[ind].end(), RB) - lower_bound(vec[ind].begin(), vec[ind].end(), LB);
	}
	if (ql > r || qr < l) return 0;
	int m = (l + r) / 2;
	return query(ind*2, l, m, ql, qr) + query(ind * 2 + 1, m+1, r, ql, qr);
}

signed main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> q;
	for (int i=1; i<=n; i++) {
		cin >> arr[i];
	}
	
	sort(arr+1, arr+n+1);
	
	
	for (int i=1; i<=n; i++) {
		string s = arr[i];
		reverse(s.begin(), s.end());
		proc.push_back({s, i});
	}
	
	proc.push_back({"", -1});
	
	sort(proc.begin(), proc.end());
	
	build(1, 1, n);
	
	while (q--) {
		
		
		cin >> pre >> suf;
		
		reverse(suf.begin(), suf.end());
		
		usep = true;
		int pre_a = first();
		pre += 'a';
		int pre_b = first() - 1;
		
		usep = false;
		int suf_a = first();
		suf += 'a';
		int suf_b = first() - 1;
		
		LB = pre_a;
		RB = pre_b;
		
		if (LB > RB) {
			cout << 0 << endl;
			continue;
		}
		
		cout << query(1, 1, n, suf_a, suf_b) << endl;
	}

}

Compilation message (stderr)

selling_rna.cpp: In function 'bool after(int)':
selling_rna.cpp:14:18: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   14 |   for (int i=0; i<min(pre.size(), arr[x].size()); i++) {
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   21 |   for (int i=0; i<min(suf.size(), proc[x].first.size()); i++) {
      |                 ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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