제출 #752323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
752323		PoPularPlusPlus	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	1560 ms	137328 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

bool remender(ll a , ll b){return a%b;}

//freopen("problemname.in", "r", stdin);
//freopen("problemname.out", "w", stdout);

void solve(){
	int n,m1;
	cin >> n >> m1;
	vector<string> arr(n);
	for(int i = 0; i < n; i++)cin >> arr[i];
	sv(arr);
	map<int,vector<int>> m;
	for(int i = 0; i < n; i++){
		ll hash = 0;
		ll pow = 1;
		for(int j = arr[i].size()-1; j >= 0; j--){
			ll num;
			if(arr[i][j] == 'A')num = 0;
			else if(arr[i][j] == 'U')num = 1;
			else if(arr[i][j] == 'G')num = 2;
			else num = 3;
			hash += (pow * num) % mod;
			hash %= mod;
			pow *= 5;
			pow %= mod;
			if(!m[hash].size() || m[hash].back() != j)m[hash].pb(i);
		}
	}
	while(m1--){
		string p , q;
		cin >> p >> q;
		int pos = lower_bound(all(arr),p) - arr.begin();
		bool b = 1;
		for(int j = p.size()-1; j >= 0; j--){
			if(p[j] == 'U')continue;
			if(p[j] == 'A'){
				p[j]='C';
				b = 0;
				break;
			}
			if(p[j] == 'C'){
				p[j] = 'G';
				b=0;
				break;
			}
			if(p[j] == 'G'){
				p[j] = 'U';
				b=0;
				break;
			}
		}
		int pos1;
		if(b)pos1 = n;
		else pos1 = upper_bound(all(arr),p)-arr.begin();
		ll hash = 0;
		ll pow = 1;
		for(int j = q.size()-1; j >= 0; j--){
			ll num;
			if(q[j] == 'A')num = 0;
			else if(q[j] == 'U')num = 1;
			else if(q[j] == 'G')num = 2;
			else num = 3;
			hash += (pow * num) % mod;
			hash %= mod;
			pow *= 5;
			pow %= mod;
		}
		if(m[hash].size() == 0){
			cout << 0 << '\n';
			continue;
		}
		//cout << pos1 << ' ' << pos << '\n';
		int p1 = upper_bound(all(m[hash]),pos1)-m[hash].begin();
		int p0 = lower_bound(all(m[hash]),pos) - m[hash].begin();
		cout << p1-p0 << '\n';
	}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

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