#include <bits/stdc++.h>
#define file(name) freopen(name".inp" , " r " , stdin);freopen(name".out" , " w " , stdout)
#define faster ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
#define pii pair < int , int >
#define pdd pair < double , double >
#define fi first
#define se second
#define mii map< int , int>
#define mdd map< double , double >
#define qi queue < int >
#define dqi deque< int >
#define pf(x) push_front(x)
#define popf pop_front()
#define reset(a,val) memset(a ,val , sizeof(a) )
#define count_bit(i) __builtin_popcountll(i)
#define mask(i) ((1LL << (i)))
#define status(x, i) (((x) >> (i)) & 1)
#define set_on(x, i) ((x) | mask(i))
#define set_off(x, i) ((x) & ~mask(i))
#define endl '\n'
const int maxn = 1e6 + 6;
const int mod= 1e9 + 7;
const int INF= 1e9;
const int LOG = 20 ;
template <class T> inline T sqr(T x) { return x * x; };
template <class T> inline int Power(T x, int y)
{ if (!y) return 1; if (y & 1) return sqr(Power(x, y / 2)) % mod * x % mod; return sqr(Power(x, y / 2)) % mod; }
template<class T> bool minimize(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
inline int gcd(int x, int y)
{ return y ? gcd(y , x % y) : x;}
inline int lcm(int x, int y) { return x * y / gcd(x, y); }
using namespace std;
int n , m;
string s[maxn];
int get_val(char ch)
{
return (ch == 'A' ? 1 : ch == 'G' ? 2 : ch == 'C' ? 3 : 4);
}
struct Trie{
struct Node{
Node* child[5];
int l , r;
int exits;
Node()
{
for (int i=1 ; i<=4 ; ++i) child[i] = NULL;
l = INF ; r = -INF;
exits = 0;
}
};
Node* root;
Trie()
{
root = new Node();
};
void add(string s , int id)
{
Node* p = root;
for(int i=0 ; i<(int)s.size() ; ++i)
{
int c = get_val(s[i]);
if (p -> child[c] == NULL) p -> child[c] = new Node;
p = p -> child[c];
minimize(p -> l , id);
maximize(p -> r , id);
}
p -> exits++;
}
pii get_range(string s)
{
Node* p = root;
for (int i=0 ; i< (int)s.size() ; ++i)
{
int c = get_val(s[i]);
if (p->child[c] == NULL) return {-1 , -1};
p = p->child[c];
}
return {p->l , p->r};
}
};
struct RTrie{
struct Node{
Node* child[5];
vector<int> exits;
Node()
{
for (int i=1 ; i<=4 ; ++i) child[i] = NULL;
exits.clear();
}
};
Node* root;
RTrie()
{
root = new Node;
};
void add(string s , int id)
{
Node* p = root;
for (int i=0 ; i<(int)s.size() ; ++i)
{
int c = get_val(s[i]);
if (p->child[c] == NULL) p->child[c] = new Node;
p = p->child[c];
p->exits.push_back(id);
}
}
int get_ans(string s , int u , int v)
{
Node* p = root;
for (int i=0 ; i< (int)s.size() ; ++i)
{
int c = get_val(s[i]);
if (p->child[c] == NULL) return 0;
p = p->child[c];
}
sort(p -> exits.begin() , p->exits.end());
// for (int x : p->exits) cout << x << " " ; cout << endl;
int l = lower_bound(p -> exits.begin() , p->exits.end() , u) - (p -> exits.begin());
int r = upper_bound(p -> exits.begin() , p->exits.end() , v) - (p -> exits.begin()) - 1;
return r - l + 1;
}
};
void solve()
{
cin >> n >> m ;
for (int i=1 ; i<=n ; ++i) cin >> s[i];
sort(s+1 , s+n+1);
Trie tr;
RTrie Rtr;
for (int i=1 ; i<=n ; ++i)
{
tr.add(s[i] , i);
reverse(s[i].begin() , s[i].end());
Rtr.add(s[i] , i);
}
while (m--)
{
string a , b ; cin >> a >> b;
pii it = tr.get_range(a);
// cout << it.fi << " " <<it.se << endl;
reverse(b.begin() , b.end());
if (it.fi == -1) cout << 0 << '\n';
else cout << Rtr.get_ans(b , it.fi , it.se) << '\n';
}
}
int32_t main()
{
faster;
#ifndef ONLINE_JUDGE
file("txt");
#else
// online submission
#endif
// int t ; cin >> t ; while (t--)
solve();
return 0;
}
Compilation message
selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:3:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
3 | #define file(name) freopen(name".inp" , " r " , stdin);freopen(name".out" , " w " , stdout)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:192:5: note: in expansion of macro 'file'
192 | file("txt");
| ^~~~
selling_rna.cpp:3:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
3 | #define file(name) freopen(name".inp" , " r " , stdin);freopen(name".out" , " w " , stdout)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:192:5: note: in expansion of macro 'file'
192 | file("txt");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
31576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
31656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
31800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
31576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
