Submission #343200

#	Time	Username	Problem	Language	Result	Execution time	Memory
343200		Parsa_PG	Selling RNA Strands (JOI16_selling_rna)	C++14	60 / 100	1571 ms	25324 KiB

selling_rna

/* Rastegary Az Shoroe Ye EDAST */
#include <bits/stdc++.h>
     
#define pb push_back
#define endl "\n"
#define ll long long
 
using namespace std;
 
const int maxn = 1e5 + 10 , Maxn = 1e5 + 10, lg = 22; 
const int mod = 22777;
const ll inf = 1e18 + 10;

string s[maxn] , p[maxn] , q[maxn];
 
int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n , m;
	cin >> n >> m;
	for(int i = 0 ; i < n ; i++)
		cin >> s[i];
	for(int i = 0 ; i < m ; i++){
		cin >> p[i] >> q[i];
		reverse(q[i].begin() , q[i].end());
	}
	int l1[maxn] , r1[maxn];
	sort(s , s+n);
	vector<pair<string , int>>v;
	for(int i = 0 ; i < m ; i++){
		l1[i] = lower_bound(s , s + n , p[i]) - s;
		p[i][p[i].size() - 1]++;
		r1[i] = lower_bound(s , s + n , p[i]) - s;
	}
	for(int i = 0 ; i < n ; i++){
		reverse(s[i].begin() , s[i].end());
		v.pb({s[i] , i});
	}
	sort(v.begin() , v.end());
	int in[maxn];
	in[n] = -1;
	for(int i = 0 ; i < n ; i ++)
		s[i] = v[i].first , in[v[i].second] = i;
	int l2[maxn] , r2[maxn];
	for(int i = 0 ; i < m ; i++){
		l2[i] = lower_bound(s , s + n , q[i]) - s;
		q[i][q[i].size() - 1]++;
		r2[i] = lower_bound(s , s + n , q[i]) - s;
	}
	for(int i = 0 ; i < m ; i++){
		int ans = 0;
		for(int j = l1[i] ; j < r1[i] ; j++)
			if(l2[i] <= in[j] && in[j] < r2[i])
				ans++;
		cout << ans << endl;
	}
	return 0;
}

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