#include <bits/stdc++.h>
using namespace std;
const int MAXL = 5;
const int MAXN = 100010;
const int MAXS = 2000010;
char bases[] = "AGCU";
class Trie
{
public:
int conv(char c)
{
for(int i = 0 ; i < 4 ; i++)
if( bases[i] == c ) return i;
}
void addString(string& s, int ind)
{
int cur = 0;
for(int i = 0 ; i < (int)s.size() ; i++)
{
int c = conv( s[i] );
if( tree[cur][c] == 0 )
tree[cur][c] = ++cnt;
cur = tree[cur][c];
allInd[cur].push_back( ind );
}
}
void getInterval(string& s, int& L, int& R)
{
L = R = 0;
int cur = 0;
for(int i = 0 ; i < (int)s.size() ; i++)
{
int c = conv( s[i] );
if( tree[cur][c] == 0 )
return;
cur = tree[cur][c];
}
L = allInd[cur].front();
R = allInd[cur].back();
}
int getQtdInterval(string& s, int L, int R)
{
int cur = 0;
for(int i = 0 ; i < (int)s.size() ; i++)
{
int c = conv( s[i] );
if( tree[cur][c] == 0 )
return 0;
cur = tree[cur][c];
}
auto itR = upper_bound( allInd[cur].begin() , allInd[cur].end() , R );
auto itL = lower_bound( allInd[cur].begin() , allInd[cur].end() , L );
return itR - itL;
}
Trie() : cnt(1) {}
protected:
int cnt;
int tree[MAXS][MAXL];
vector<int> allInd[MAXS];
};
int n, q;
string s[MAXN];
Trie prefixTrie, suffixTrie;
int main()
{
cin >> n >> q;
for(int i = 1 ; i <= n ; i++)
cin >> s[i];
sort( s + 1 , s + n + 1 );
for(int i = 1 ; i <= n ; i++)
{
prefixTrie.addString( s[i] , i );
reverse( s[i].begin() , s[i].end() );
suffixTrie.addString( s[i] , i );
}
for(int i = 1 ; i <= q ; i++)
{
string prefix, suffix;
cin >> prefix >> suffix;
reverse( suffix.begin() , suffix.end() );
int L, R;
prefixTrie.getInterval( prefix , L , R );
printf("%d\n",suffixTrie.getQtdInterval( suffix , L , R ));
}
}
Compilation message
selling_rna.cpp: In member function 'int Trie::conv(char)':
selling_rna.cpp:19:3: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
97416 KB |
Output is correct |
2 |
Correct |
63 ms |
97400 KB |
Output is correct |
3 |
Correct |
59 ms |
97420 KB |
Output is correct |
4 |
Correct |
55 ms |
97400 KB |
Output is correct |
5 |
Correct |
57 ms |
97400 KB |
Output is correct |
6 |
Correct |
54 ms |
97400 KB |
Output is correct |
7 |
Correct |
54 ms |
97400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
487 ms |
215824 KB |
Output is correct |
2 |
Correct |
504 ms |
209860 KB |
Output is correct |
3 |
Correct |
534 ms |
214008 KB |
Output is correct |
4 |
Correct |
472 ms |
208744 KB |
Output is correct |
5 |
Correct |
412 ms |
225732 KB |
Output is correct |
6 |
Correct |
423 ms |
227584 KB |
Output is correct |
7 |
Correct |
385 ms |
121848 KB |
Output is correct |
8 |
Correct |
576 ms |
190712 KB |
Output is correct |
9 |
Correct |
535 ms |
177528 KB |
Output is correct |
10 |
Correct |
398 ms |
173660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
223 ms |
99252 KB |
Output is correct |
2 |
Correct |
173 ms |
99192 KB |
Output is correct |
3 |
Correct |
188 ms |
99064 KB |
Output is correct |
4 |
Correct |
168 ms |
99064 KB |
Output is correct |
5 |
Correct |
159 ms |
99064 KB |
Output is correct |
6 |
Correct |
187 ms |
99192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
97416 KB |
Output is correct |
2 |
Correct |
63 ms |
97400 KB |
Output is correct |
3 |
Correct |
59 ms |
97420 KB |
Output is correct |
4 |
Correct |
55 ms |
97400 KB |
Output is correct |
5 |
Correct |
57 ms |
97400 KB |
Output is correct |
6 |
Correct |
54 ms |
97400 KB |
Output is correct |
7 |
Correct |
54 ms |
97400 KB |
Output is correct |
8 |
Correct |
487 ms |
215824 KB |
Output is correct |
9 |
Correct |
504 ms |
209860 KB |
Output is correct |
10 |
Correct |
534 ms |
214008 KB |
Output is correct |
11 |
Correct |
472 ms |
208744 KB |
Output is correct |
12 |
Correct |
412 ms |
225732 KB |
Output is correct |
13 |
Correct |
423 ms |
227584 KB |
Output is correct |
14 |
Correct |
385 ms |
121848 KB |
Output is correct |
15 |
Correct |
576 ms |
190712 KB |
Output is correct |
16 |
Correct |
535 ms |
177528 KB |
Output is correct |
17 |
Correct |
398 ms |
173660 KB |
Output is correct |
18 |
Correct |
223 ms |
99252 KB |
Output is correct |
19 |
Correct |
173 ms |
99192 KB |
Output is correct |
20 |
Correct |
188 ms |
99064 KB |
Output is correct |
21 |
Correct |
168 ms |
99064 KB |
Output is correct |
22 |
Correct |
159 ms |
99064 KB |
Output is correct |
23 |
Correct |
187 ms |
99192 KB |
Output is correct |
24 |
Correct |
537 ms |
196480 KB |
Output is correct |
25 |
Correct |
600 ms |
196728 KB |
Output is correct |
26 |
Correct |
501 ms |
195576 KB |
Output is correct |
27 |
Correct |
506 ms |
195320 KB |
Output is correct |
28 |
Correct |
665 ms |
132952 KB |
Output is correct |
29 |
Correct |
499 ms |
110692 KB |
Output is correct |