oj.uz

Submission #378108

# Submission time Handle Problem Language Result Execution time Memory
378108 2021-03-16T03:19:34 Z reymontada61 Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 16600 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3436 KB Output is correct
2 Correct 3 ms 3436 KB Output is correct
3 Correct 3 ms 3456 KB Output is correct
4 Correct 4 ms 3436 KB Output is correct
5 Correct 3 ms 3436 KB Output is correct
6 Correct 3 ms 3436 KB Output is correct
7 Correct 3 ms 3436 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 11628 KB Output is correct
2 Correct 118 ms 11744 KB Output is correct
3 Correct 117 ms 11756 KB Output is correct
4 Correct 133 ms 11720 KB Output is correct
5 Correct 40 ms 8776 KB Output is correct
6 Correct 39 ms 8776 KB Output is correct
7 Correct 101 ms 12268 KB Output is correct
8 Correct 101 ms 13640 KB Output is correct
9 Correct 115 ms 13640 KB Output is correct
10 Correct 103 ms 11372 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1373 ms 6496 KB Output is correct
2 Correct 248 ms 5220 KB Output is correct
3 Correct 364 ms 6624 KB Output is correct
4 Correct 406 ms 6496 KB Output is correct
5 Correct 546 ms 5348 KB Output is correct
6 Correct 844 ms 6496 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3436 KB Output is correct
2 Correct 3 ms 3436 KB Output is correct
3 Correct 3 ms 3456 KB Output is correct
4 Correct 4 ms 3436 KB Output is correct
5 Correct 3 ms 3436 KB Output is correct
6 Correct 3 ms 3436 KB Output is correct
7 Correct 3 ms 3436 KB Output is correct
8 Correct 78 ms 11628 KB Output is correct
9 Correct 118 ms 11744 KB Output is correct
10 Correct 117 ms 11756 KB Output is correct
11 Correct 133 ms 11720 KB Output is correct
12 Correct 40 ms 8776 KB Output is correct
13 Correct 39 ms 8776 KB Output is correct
14 Correct 101 ms 12268 KB Output is correct
15 Correct 101 ms 13640 KB Output is correct
16 Correct 115 ms 13640 KB Output is correct
17 Correct 103 ms 11372 KB Output is correct
18 Correct 1373 ms 6496 KB Output is correct
19 Correct 248 ms 5220 KB Output is correct
20 Correct 364 ms 6624 KB Output is correct
21 Correct 406 ms 6496 KB Output is correct
22 Correct 546 ms 5348 KB Output is correct
23 Correct 844 ms 6496 KB Output is correct
24 Correct 250 ms 12184 KB Output is correct
25 Correct 421 ms 12444 KB Output is correct
26 Correct 169 ms 12036 KB Output is correct
27 Correct 574 ms 12164 KB Output is correct
28 Execution timed out 1585 ms 16600 KB Time limit exceeded
29 Halted 0 ms 0 KB -