제출 #1101350

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

selling_rna

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 


#define getar(ar,n) for(ll i=0;i<n;++i) cin>>ar[i]
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define br cout<<"\n"
#define pb push_back
#define nl '\n'
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ret return
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())

const int mxN = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;

map<char,ll> id;

struct Node{
	Node* children[4];
	vector<ll> points;
	Node(){
		for(ll i=0;i<4;++i) children[i]=NULL;
	}
};

Node* p_root=new Node();
Node* s_root=new Node();

void add(Node* curr,string str,ll idx){
	for(auto it:str){
		if(curr->children[id[it]]==NULL) curr->children[id[it]]=new Node();
		curr=curr->children[id[it]];
		curr->points.pb(idx);
	}
} 

pair<ll,ll> qry(Node* curr,string str){
	for(auto it:str){
		if(curr->children[id[it]]==NULL) return {INF,-INF};
		curr=curr->children[id[it]];
	}
	return {curr->points[0],curr->points[curr->points.size()-1]};
}


string rev(string str){
	string ans;
	for(ll i=str.size()-1;i>=0;--i){
		ans.pb(str[i]);
	}
	return ans;
}

void solve() {
    ll n,m;cin>>n>>m;
    vector<string> full_str(n);
    for(auto &it:full_str) cin>>it;
    sort(all(full_str));
	id['A']=0;
	id['C']=1;
	id['G']=2;
	id['U']=3;
	
	ll idx=1;
	for(auto it:full_str){
		add(p_root,it,idx);
		add(s_root,rev(it),idx++);
	}
	for(ll i=0;i<m;++i){
		string l,r;cin>>l>>r;
		pair<ll,ll> p_range=qry(p_root,l);
		if(p_range.first>p_range.second) cout<<0<<nl;
		else{
			bool f=0;
			Node* curr=s_root;
			for(auto it:rev(r)){
				if(curr->children[id[it]]==NULL){
					cout<<0<<nl;
					f=1;
					break;
				}
				curr=curr->children[id[it]];
			}
			if(!f){
				ll l=lower_bound(all(curr->points),p_range.first)-curr->points.begin();
				ll r=upper_bound(all(curr->points),p_range.second)-curr->points.begin();
				cout<<r-l<<nl;
			}
		}
	}
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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