// cre: Nguyen Hoang Hung - Train VOI 2024
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define debug(x) { cerr << #x << " = "; cerr << (x) << endl; }
#define PR(a,n) { cerr << #a << " = "; FOR(_,1,n) cerr << a[_] << ' '; cerr << endl; }
#define PR0(a,n) { cerr << #a << " = "; REP(_,n) cerr << a[_] << ' '; cerr << endl; }
#define bit(X, i) ((X >> i) & 1)
#define cntbit(X) __builtin_popcountll(X)
#define fi first
#define se second
#define pb push_back
#define all(X) begin(X), end(X)
#define SZ(X) ((int)(X).size())
#define RR(X) X.resize(unique(all(X)) - begin(X))
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
template <typename T>
bool maximize(T &x, T y)
{
if(x < y)
x = y;
else
return 0;
return 1;
}
template <typename T>
bool minimize(T &x, T y)
{
if(x > y)
x = y;
else
return 0;
return 1;
}
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
ll Rand(ll l, ll r) { return l + rand() % (r - l + 1); }
const int maxN = 2e6;
const ll inf = 1e18+7;
const int MOD = 1e9 + 7;
const double PI = acos(-1);
/*
-------------------------------------------------------------------------------------
END OF TEMPLATE
-------------------------------------------------------------------------------------
Nguyen Hoang Hung - catlover
Training for VOI24 gold medal
-------------------------------------------------------------------------------------
*/
int convert(char c)
{
if(c == 'A') return 0;
if(c == 'U') return 1;
if(c == 'G') return 2;
return 3;
}
/////////////////////////////////////////////////////////
/**
BUILD TRIE
**/
struct Trie
{
Trie *ch[4];
vector<int> vt;
int tin, tout;
Trie()
{
FOR(i, 0, 3) ch[i] = NULL;
tin = tout = 0;
vt.resize(0);
}
} T, rev_T;
int pos[maxN+5];
void add(string s, int id)
{
Trie *p = &T;
for(char x : s)
{
int c = convert(x);
if(p->ch[c] == NULL) p->ch[c] = new Trie;
p = p->ch[c];
}
p->vt.pb(id);
}
void rev_add(string s, int id)
{
Trie *p = &rev_T;
for(char x : s)
{
int c = convert(x);
if(p->ch[c] == NULL) p->ch[c] = new Trie;
p = p->ch[c];
p->vt.pb(pos[id]);
}
}
/////////////////////////////////////////////////////////
/**
EULER TOUR
**/
int Time = 0;
void dfs(Trie *p)
{
p->tin = ++Time;
if(SZ(p->vt) > 0)
{
for(int x : p->vt) pos[x] = Time;
}
FOR(i, 0, 3)
if(p->ch[i] != NULL) dfs(p->ch[i]);
p->tout = Time;
}
void dfs_rev(Trie *p)
{
sort(all(p->vt));
FOR(i, 0, 3)
if(p->ch[i] != NULL) dfs(p->ch[i]);
}
pii getRange(string s)
{
Trie *p = &T;
for(char x : s)
{
int c = convert(x);
if(p->ch[c] == NULL) return make_pair(0, 0);
p = p->ch[c];
}
return make_pair(p->tin, p->tout);
}
int getAns(string s, pii Range)
{
Trie *p = &rev_T;
for(char x : s)
{
int c = convert(x);
if(p->ch[c] == NULL) return 0;
p = p->ch[c];
}
int le = lower_bound(all(p->vt), Range.fi) - p->vt.begin();
int ri = upper_bound(all(p->vt), Range.se) - p->vt.begin() - 1;
return ri - le + 1;
}
string s[maxN+5];
void solve() {
int N, M; cin >> N >> M;
FOR(i, 1, N)
{
cin >> s[i];
add(s[i], i);
reverse(all(s[i]));
}
dfs(&T);
FOR(i, 1, N)
{
rev_add(s[i], i);
}
dfs_rev(&rev_T);
while(M --> 0)
{
string P, Q;
cin >> P >> Q;
reverse(all(Q));
pii Range = getRange(P);
// cout << Range.fi << ' ' << Range.se << endl;
cout << getAns(Q, Range) << '\n';
}
}
void solve_TestCase() {
int testcase; cin >> testcase;
while(testcase --> 0)
{
solve();
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
file("RNA");
// solve_TestCase();
solve();
cerr << "\nTime : " << clock()/1000.0 << "s\n";
return 0;
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:22:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:208:5: note: in expansion of macro 'file'
208 | file("RNA");
| ^~~~
selling_rna.cpp:22:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:208:5: note: in expansion of macro 'file'
208 | file("RNA");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
64092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
220 ms |
283156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
65752 KB |
Output is correct |
| 2 |
Incorrect |
24 ms |
65880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
64092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
