제출 #947452

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
947452		pcc	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	234 ms	57684 KiB

selling_rna

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define bs basic_string<int>

const int mxn = 1e5+10;


int N,Q;
basic_string<int> arr[mxn];
vector<pair<basic_string<int>,int>> op[mxn];
int ans[mxn];

struct node{
	int ch[4];
	int dp;
};

int ppp = 0;
int newnode(){
	return ++ppp;
}

node trie[mxn*100];
int rt;

void add(bs s){
	int now = rt;
	for(auto &i:s){
		if(!trie[now].ch[i])trie[now].ch[i] = newnode();
		now = trie[now].ch[i];
		trie[now].dp++;
	}
	return;
}
int getans(basic_string<int> s){
	int now = rt;
	for(auto &i:s){
		now = trie[now].ch[i];
	}
	return trie[now].dp;
}

basic_string<int> conv(string s){
	basic_string<int> re;
	for(auto &i:s){
		if(i == 'A')re += 0;
		else if(i == 'C')re += 1;
		else if(i == 'G')re += 2;
		else re += 3;
	}
	return re;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	rt = newnode();
	cin>>N>>Q;
	for(int i = 1;i<=N;i++){
		string s;
		cin>>s;
		arr[i] = conv(s);
	}
	sort(arr+1,arr+N+1);
	for(int i = 1;i<=Q;i++){
		string sa,sb;
		cin>>sa>>sb;
		auto ta = conv(sa),tb = conv(sb);
		reverse(tb.begin(),tb.end());
		auto lit = lower_bound(arr+1,arr+N+1,ta)-arr;
		ta.back()++;
		auto rit = lower_bound(arr+1,arr+N+1,ta)-arr;
		op[lit].push_back(make_pair(tb,i));
		op[rit].push_back(make_pair(tb,-i));
	}
	for(int i = N;i>=1;i--){
		reverse(arr[i].begin(),arr[i].end());
		add(arr[i]);
		for(auto &j:op[i]){
			if(j.sc>0){
				ans[j.sc] += getans(j.fs);
			}
			else ans[-j.sc] -= getans(j.fs);
		}
	}
	for(int i = 1;i<=Q;i++)cout<<ans[i]<<'\n';
	return 0;
}

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