#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using vss = vector<vs>;
using vb = vector<bool>;
using vbb = vector<vb>;
using ii = pair<int, int>;
using vpi = vector<ii>;
using vpii = vector<vpi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using table = unordered_map<unsigned long, int>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vpll = vector<vpl>;
#define f first
#define s second
#define forn(i, n) for(int i = 0; i < n; i++)
#define fore(i, a, b) for(int i = a; i <= b; i++)
#define for1n(i, n) for(int i = 1; i <= n; i++)
#define rof(i, n) for(int i = n-1; i >= 0; i--)
#define rofe(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define dsc(type) greater<type>
#define Flag cout << "Reached here.\n"
#define FASTIO ios::sync_with_stdio(0); cin.tie(0);
#define pb push_back
#define pbb pop_back
#define sz size
#define rsz resize
#define rsv reserve
#define ins insert
#define lb(a, val) lower_bound(all(a), val);
#define ub(a, val) upper_bound(all(a), val);
#define onec(x) __builtin_popcount(x)
#define end0(x) __builtin_clz(x)
#define beg0(x) __builtin_ctz(x)
#define MAX 1000000000
#define MIN -MAX
#define mod 1000000007LL
#define clr(x, y) memset(x, y, sizeof(x))
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};
ll binpow(ll a, ll b) {
a %= mod;
ll res = 1;
while (b > 0) {
if (b & 1) res *= a, res %= mod;
a *= a, a %= mod;
b >>= 1;
}
return res;
}
vi fct(ll n) {
vi fac;
while(n%2 == 0) n /= 2, fac.pb(2);
for(int i = 3; i * i <= n; i += 2)
while(n%i == 0) fac.pb(i), n /= i;
if(n > 1) fac.pb(n);
return fac;
}
ll gcd(ll a, ll b) {
if (b == 0) return a;
return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
return (a*b) / gcd(a, b);
}
#define maxN 100001
#define maxSM 100005
int getc(char c) {
if(c == 'A') return 0;
else if(c == 'G') return 1;
else if(c == 'C') return 2;
else return 3;
}
class trie1 {
vpii rng;
vii t;
int sz;
public:
trie1() {
rng = vpii(maxSM, vpi(4, {-1, -1}));
t = vii(maxSM, vi(4, -1));
sz = 1;
}
void ins(string& s, int ind) {
int v = 0;
forn(i, s.sz()) {
int c = getc(s[i]);
if(t[v][c] == -1) t[v][c] = sz++, rng[v][c] = {ind, ind-1};
rng[v][c].s++;
v = t[v][c];
}
}
pair<int, int> q(string& s) {
int v = 0;
forn(i, s.sz()) {
int c = getc(s[i]);
if(t[v][c] == -1) return {-1, -1};
if(i == s.sz()-1) return rng[v][c];
v = t[v][c];
}
//Not reachable
return {-1, -1};
}
};
class trie2 {
vector<vii> rng;
vii t;
int sz;
public:
trie2() {
rng = vector<vii>(maxSM, vii(4));
t = vii(maxSM, vi(4, -1));
sz = 1;
}
void ins(string& s, int ind) {
int v = 0;
forn(i, s.sz()) {
int c = getc(s[i]);
if(t[v][c] == -1) t[v][c] = sz++;
rng[v][c].pb(ind);
v = t[v][c];
}
}
int q(string& s, ii& q) {
int v = 0;
forn(i, s.sz()) {
int c = getc(s[i]);
if(t[v][c] == -1) return 0;
if(i == s.sz()-1) return upper_bound(all(rng[v][c]), q.s) - lower_bound(all(rng[v][c]), q.f);
v = t[v][c];
}
}
void srt(string& s) {
int v = 0;
forn(i, s.sz()) {
int c = getc(s[i]);
sort(all(rng[v][c]));
v = t[v][c];
}
}
};
void first3(int n, int m, vs& s, vs& p, vs& q) {
sort(all(s));
trie1 t1;
trie2 t2;
forn(i, n) {
t1.ins(s[i], i);
reverse(all(s[i]));
t2.ins(s[i], i);
}
forn(i, n) t2.srt(s[i]);
forn(i, m) {
auto one = t1.q(p[i]);
auto two = t2.q(q[i], one);
cout << two << '\n';
}
}
void solve() {
int n, m;
cin >> n >> m;
vs s(n);
forn(i, n) cin >> s[i];
vs p(m), q(m);
forn(i, m) {
cin >> p[i] >> q[i];
reverse(all(q[i]));
}
int sm = 0;
forn(i, n) sm += s[i].sz();
if(sm <= 100005) first3(n, m, s, p, q);
}
int main() {
FASTIO;
solve();
}
Compilation message
selling_rna.cpp: In member function 'void trie1::insert(std::string&, int)':
selling_rna.cpp:24:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | #define forn(i, n) for(int i = 0; i < n; i++)
......
114 | forn(i, s.sz()) {
| ~~~~~~~~~
selling_rna.cpp:114:5: note: in expansion of macro 'forn'
114 | forn(i, s.sz()) {
| ^~~~
selling_rna.cpp: In member function 'std::pair<int, int> trie1::q(std::string&)':
selling_rna.cpp:24:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | #define forn(i, n) for(int i = 0; i < n; i++)
......
123 | forn(i, s.sz()) {
| ~~~~~~~~~
selling_rna.cpp:123:5: note: in expansion of macro 'forn'
123 | forn(i, s.sz()) {
| ^~~~
selling_rna.cpp:126:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | if(i == s.sz()-1) return rng[v][c];
| ~~^~~~~~~~~~~
selling_rna.cpp: In member function 'void trie2::insert(std::string&, int)':
selling_rna.cpp:24:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | #define forn(i, n) for(int i = 0; i < n; i++)
......
148 | forn(i, s.sz()) {
| ~~~~~~~~~
selling_rna.cpp:148:5: note: in expansion of macro 'forn'
148 | forn(i, s.sz()) {
| ^~~~
selling_rna.cpp: In member function 'int trie2::q(std::string&, ii&)':
selling_rna.cpp:24:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | #define forn(i, n) for(int i = 0; i < n; i++)
......
158 | forn(i, s.sz()) {
| ~~~~~~~~~
selling_rna.cpp:158:5: note: in expansion of macro 'forn'
158 | forn(i, s.sz()) {
| ^~~~
selling_rna.cpp:161:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | if(i == s.sz()-1) return upper_bound(all(rng[v][c]), q.s) - lower_bound(all(rng[v][c]), q.f);
| ~~^~~~~~~~~~~
selling_rna.cpp: In member function 'void trie2::srt(std::string&)':
selling_rna.cpp:24:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | #define forn(i, n) for(int i = 0; i < n; i++)
......
167 | forn(i, s.sz()) {
| ~~~~~~~~~
selling_rna.cpp:167:5: note: in expansion of macro 'forn'
167 | forn(i, s.sz()) {
| ^~~~
selling_rna.cpp: In member function 'int trie2::q(std::string&, ii&)':
selling_rna.cpp:164:1: warning: control reaches end of non-void function [-Wreturn-type]
164 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
31580 KB |
Output is correct |
| 2 |
Correct |
28 ms |
31632 KB |
Output is correct |
| 3 |
Correct |
26 ms |
31572 KB |
Output is correct |
| 4 |
Correct |
28 ms |
31516 KB |
Output is correct |
| 5 |
Correct |
28 ms |
31552 KB |
Output is correct |
| 6 |
Correct |
27 ms |
31636 KB |
Output is correct |
| 7 |
Correct |
28 ms |
31564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
5868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1588 ms |
37392 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
31580 KB |
Output is correct |
| 2 |
Correct |
28 ms |
31632 KB |
Output is correct |
| 3 |
Correct |
26 ms |
31572 KB |
Output is correct |
| 4 |
Correct |
28 ms |
31516 KB |
Output is correct |
| 5 |
Correct |
28 ms |
31552 KB |
Output is correct |
| 6 |
Correct |
27 ms |
31636 KB |
Output is correct |
| 7 |
Correct |
28 ms |
31564 KB |
Output is correct |
| 8 |
Incorrect |
8 ms |
5868 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
