oj.uz

Submission #1100159

# Submission time Handle Problem Language Result Execution time Memory
1100159 2024-10-13T05:47:30 Z rayan_bd Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 87904 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(),x.end()
#define pb push_back
#define ll long long
const int mxN = 1e5;

unordered_map<char,ll> mp;
vector<ll> emp;

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

struct Trie{
	Node* root = new Node();
	void add(string str){
		Node* curr = root;
		for(auto it:str){
			if(curr->children[mp[it]]==NULL) curr->children[mp[it]]=new Node();
			curr=curr->children[mp[it]];
		}
		curr->end=1;
	}
	void update_pos(string str,bool from_beg,ll idx){
		Node* curr=root;
		if(!from_beg){
			for(int i=str.size()-1;i>=0;--i){
				char it=str[i];
				if(curr->children[mp[it]]==NULL) return;
				curr=curr->children[mp[it]];
				if(curr->end){
					curr->end_pos.pb(idx);
				}
			}
			return;
		}
		for(auto it:str){
			if(curr->children[mp[it]]==NULL) return;
			curr=curr->children[mp[it]];
			if(curr->end){
				curr->end_pos.pb(idx);
			}
		}
	}
	vector<ll> qry(string str){
		Node* curr = root;
		for(auto it:str){
			curr=curr->children[mp[it]];
		}
		return curr->end_pos;
	}
};

void solve(){
	mp['A']=0;
	mp['C']=1;
	mp['G']=2;
	mp['U']=3;

	Trie pre,suf;
	ll n,m;cin>>n>>m;
	vector<string> vec(n);
	vector<pair<string,string>> pr(m);
	for(ll i=0;i<n;++i){
		cin>>vec[i];
	}
	for(ll i=0;i<m;++i){
		cin>>pr[i].first>>pr[i].second;
		pre.add(pr[i].first);
		reverse(all(pr[i].second));
		suf.add(pr[i].second);
	}
	ll idx=0;
	for(auto it:vec){
		pre.update_pos(it,1,idx);
		suf.update_pos(it,0,idx);
		++idx;
	}
	for(auto it:pr){
		vector<ll> c1=pre.qry(it.first);
		vector<ll> c2=suf.qry(it.second);
		if(c1.size()>c2.size()) swap(c1,c2);
		ll ans=0,nwst=0;
		if(c1.size()==0||c2.size()==0){
			cout<<ans<<'\n';
			continue;
		}
		for(auto it:c1){
			ll st=nwst,en=c2.size()-1;
			while(st<=en){
				ll mid=(st+en)/2;
				if(c2[mid]==it){
					++ans;
					nwst=mid+1;
					break;
				}
				if(c2[mid]>it) en=mid-1;
				else st=mid+1;
			}
		}
		cout<<ans<<'\n';
	}
}

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

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 21364 KB Output is correct
2 Correct 124 ms 29416 KB Output is correct
3 Correct 106 ms 26208 KB Output is correct
4 Correct 123 ms 29152 KB Output is correct
5 Correct 82 ms 77664 KB Output is correct
6 Correct 83 ms 76756 KB Output is correct
7 Correct 191 ms 41568 KB Output is correct
8 Correct 146 ms 87904 KB Output is correct
9 Correct 143 ms 81248 KB Output is correct
10 Correct 347 ms 19248 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1538 ms 6988 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 612 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 360 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 0 ms 360 KB Output is correct
7 Correct 1 ms 360 KB Output is correct
8 Correct 73 ms 21364 KB Output is correct
9 Correct 124 ms 29416 KB Output is correct
10 Correct 106 ms 26208 KB Output is correct
11 Correct 123 ms 29152 KB Output is correct
12 Correct 82 ms 77664 KB Output is correct
13 Correct 83 ms 76756 KB Output is correct
14 Correct 191 ms 41568 KB Output is correct
15 Correct 146 ms 87904 KB Output is correct
16 Correct 143 ms 81248 KB Output is correct
17 Correct 347 ms 19248 KB Output is correct
18 Execution timed out 1538 ms 6988 KB Time limit exceeded
19 Halted 0 ms 0 KB -