Submission #378108

#	Time	Username	Problem	Language	Result	Execution time	Memory
378108		reymontada61	Selling RNA Strands (JOI16_selling_rna)	C++14	60 / 100	1585 ms	16600 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;
}

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());
	
	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;
		
		int ans = 0;
		
		for (int x=suf_a; x<=suf_b; x++) {
			if (pre_a <= proc[x].second && proc[x].second <= pre_b) ans++;
		}
		
		cout << ans << 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: 0 / 40