oj.uz

Submission #716387

# Submission time Handle Problem Language Result Execution time Memory
716387 2023-03-30T01:06:39 Z Hyojin Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 190 ms 194208 KB 
#include <bits/stdc++.h>
using namespace std;
#define bit(n,i) ((n>>i)&1)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define ep emplace_back
#define pii pair<int,int>
#define piii pair<int,pii>
#define fi first
#define se second
#define ll long long
const int MOD=1e9+7;
const int base=31;
const int N=1e5+5;
int n,q;
string v[N];
int val(char c)
{
	if (c=='A') return 0;
	if (c=='G') return 1;
	if (c=='C') return 2;
	return 3;
}
struct Trie
{
	int l,r;
	Trie *child[4];
	Trie()
	{
		l=1e9,r=-1e9;
		memset(child,0,sizeof child);
	}
};
Trie root;
void trieAdd(const string &s,int pos)
{
	Trie *p=&root;
	int n=s.size();
	for (int i=0;i<n;i++)
	{
		int c=val(s[i]);
		if (!p->child[c]) p->child[c]=new Trie();
		p=p->child[c];
		p->l=min(p->l,pos);
		p->r=max(p->r,pos);
	}
}
pair<int,int>getRange(const string &s)
{
	Trie *p=&root;
	int n=s.size();
	for (int i=0;i<n;i++)
	{
		int c=val(s[i]);
		if (!p->child[c]) return {0,0};
		p=p->child[c];
	}
	return {p->l,p->r};
}
struct revTrie
{
	revTrie *child[4];
	vector<int>vi;
	revTrie()
	{
		vi.clear();
		memset(child,0,sizeof child);
	}
};
revTrie r;
void revAdd(const string &s,int pos)
{
	revTrie *p=&r;
	int n=s.size();
	for (int i=n-1;~i;i--)
	{
		int c=val(s[i]);
		if (!p->child[c]) p->child[c]=new revTrie();
		p=p->child[c];
		p->vi.pb(pos);
	}
}
int revFind(const string &s,pair<int,int>range)
{
	revTrie *p=&r;
	int n=s.size();
	for (int i=n-1;~i;i--)
	{
		int c=val(s[i]);
		p=p->child[c];
	}
	int it1=lower_bound(all(p->vi),range.fi)-(p->vi.begin());
	int it2=upper_bound(all(p->vi),range.se)-(p->vi.begin());
	return it2-it1;
}
int main()
{
	#ifdef Hyojin
    	freopen("input.txt", "r", stdin);
    	freopen("output.txt", "w", stdout);
	#endif //Hyojin
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for (int i=1;i<=n;i++)
	{
		cin>>v[i];
	}
	sort(v+1,v+n+1);
	for (int i=1;i<=n;i++)
	{
		trieAdd(v[i],i);
	}
	for (int i=1;i<=n;i++)
	{
		revAdd(v[i],i);
	}
	while (q--)
	{
		string p,q;
		cin>>p>>q;
		pair<int,int>x=getRange(p);
		if (x.se==0) cout<<0;
		else
		{
			int ans=revFind(q,x);
			cout<<ans;
		}
		cout<<"\n";
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3460 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3456 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 194208 KB Output is correct
2 Correct 187 ms 184340 KB Output is correct
3 Correct 122 ms 111788 KB Output is correct
4 Correct 120 ms 106884 KB Output is correct
5 Correct 175 ms 178620 KB Output is correct
6 Correct 179 ms 181252 KB Output is correct
7 Correct 48 ms 19148 KB Output is correct
8 Correct 155 ms 117820 KB Output is correct
9 Correct 134 ms 101288 KB Output is correct
10 Correct 103 ms 96148 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4688 KB Output is correct
2 Correct 18 ms 4724 KB Output is correct
3 Correct 25 ms 4708 KB Output is correct
4 Correct 21 ms 4504 KB Output is correct
5 Correct 20 ms 4728 KB Output is correct
6 Correct 23 ms 4684 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3460 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3456 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 183 ms 194208 KB Output is correct
9 Correct 187 ms 184340 KB Output is correct
10 Correct 122 ms 111788 KB Output is correct
11 Correct 120 ms 106884 KB Output is correct
12 Correct 175 ms 178620 KB Output is correct
13 Correct 179 ms 181252 KB Output is correct
14 Correct 48 ms 19148 KB Output is correct
15 Correct 155 ms 117820 KB Output is correct
16 Correct 134 ms 101288 KB Output is correct
17 Correct 103 ms 96148 KB Output is correct
18 Correct 22 ms 4688 KB Output is correct
19 Correct 18 ms 4724 KB Output is correct
20 Correct 25 ms 4708 KB Output is correct
21 Correct 21 ms 4504 KB Output is correct
22 Correct 20 ms 4728 KB Output is correct
23 Correct 23 ms 4684 KB Output is correct
24 Correct 179 ms 160508 KB Output is correct
25 Correct 190 ms 160700 KB Output is correct
26 Correct 178 ms 158704 KB Output is correct
27 Correct 119 ms 94404 KB Output is correct
28 Correct 149 ms 38604 KB Output is correct
29 Correct 64 ms 11980 KB Output is correct