oj.uz

Submission #1100158

# Submission time Handle Problem Language Result Execution time Memory
1100158 2024-10-13T05:45:55 Z rayan_bd Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 87856 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);
		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 360 KB Output is correct
2 Correct 0 ms 356 KB Output is correct
3 Correct 1 ms 360 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 21240 KB Output is correct
2 Correct 183 ms 29388 KB Output is correct
3 Correct 127 ms 26220 KB Output is correct
4 Correct 126 ms 29212 KB Output is correct
5 Correct 117 ms 77744 KB Output is correct
6 Correct 96 ms 76692 KB Output is correct
7 Correct 229 ms 41392 KB Output is correct
8 Correct 165 ms 87856 KB Output is correct
9 Correct 146 ms 81312 KB Output is correct
10 Correct 512 ms 19124 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1598 ms 7000 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 360 KB Output is correct
2 Correct 0 ms 356 KB Output is correct
3 Correct 1 ms 360 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 84 ms 21240 KB Output is correct
9 Correct 183 ms 29388 KB Output is correct
10 Correct 127 ms 26220 KB Output is correct
11 Correct 126 ms 29212 KB Output is correct
12 Correct 117 ms 77744 KB Output is correct
13 Correct 96 ms 76692 KB Output is correct
14 Correct 229 ms 41392 KB Output is correct
15 Correct 165 ms 87856 KB Output is correct
16 Correct 146 ms 81312 KB Output is correct
17 Correct 512 ms 19124 KB Output is correct
18 Execution timed out 1598 ms 7000 KB Time limit exceeded
19 Halted 0 ms 0 KB -