# include <bits/stdc++.h>
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
#define piii pair <int, pii >
using namespace std;
const int N = 2e6 + 5;
int in[4*N],out[4*N],tin,cnt[3],endd[4*N],cur,trie[2][4*N][4],le[4*N],ri[4*N],n,m,lst,curi;
string s[N],pref,suf;
int tree[4*N];
vector < piii > queries;
map <int,int> pas[4*N];
vector <pii> que;
vector <int> v[4*N];
void update(int idx, int val) {
for (int i = idx; i < N; i += i&(-i)) {
tree[i] += val;
}
}
int getans(int idx) {
int pas = 0;
for (int i = idx; i > 0; i-=i&(-i)) {
pas += tree[i];
} return pas;
}
void dfs(int a, int p) {
tin++;
in[a] = tin;
for (int i = 0; i < v[a].size(); i++) {
if (v[a][i] == p) continue;
dfs(v[a][i],a);
}
out[a] = tin;
//cout<<a<<" "<<in[a]<<" "<<out[a]<<" \n";
}
void insert(string s, int idx, int ty) {
int cur = 1;
for (int i = 0; i < s.size(); i++) {
if (trie[ty][cur][s[i]-'a'] == 0) {
cnt[ty]++;
if (ty == 1) { v[cur].pb(cnt[ty]); }
trie[ty][cur][s[i] - 'a'] = cnt[ty];
}
cur = trie[ty][cur][s[i] - 'a'];
// cout<<idx<<" "<<ty<<" "<<s[i]<<" "<<cur<<endl;
if (ty == 0) {
le[cur] = min(le[cur],idx);
ri[cur] = max(ri[cur],idx);
}
}
if (ty == 1) {
endd[idx] = cur;
}
}
pii find(string s1) {
int cur = 1;
for (int i = 0; i < s1.size(); i++) {
if (!trie[0][cur][s1[i] - 'a']) return{-1,-1};
cur = trie[0][cur][s1[i] - 'a'];
}
return {le[cur],ri[cur]};
}
int find1(string s1) {
int cur = 1;
for (int i = 0; i < s1.size(); i++) {
if (!trie[1][cur][s1[i] - 'a']) return -1;
cur = trie[1][cur][s1[i] - 'a'];
}
return cur;
}
string get(string ss) {
for (int i = 0; i < ss.size(); i++) {
if (ss[i] == 'A') ss[i] = 'a';
if (ss[i] == 'C') ss[i]= 'b';
if (ss[i] == 'G') ss[i] = 'c';
if (ss[i] == 'U') ss[i] = 'd';
}
return ss;
}
main() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for (int i = 1; i <= n; i++) {
cin>>s[i];
s[i] = get(s[i]);
}
for (int i = 1; i <= 1e6; i++) le[i] = 1e9, ri[i] = 0;
le[1] = 1; ri[n] = n;
sort(s + 1, s + n + 1);
cnt[0] = cnt[1] = 1;
for (int i = 1; i <= n; i++) {
insert(s[i], i,0);
reverse(s[i].begin(),s[i].end());
insert(s[i],i,1);
}
dfs(1,0);
for (int i = 1; i <= m; i++) {
cin>>pref>>suf;
pref = get(pref); suf = get(suf);
pii x = find(pref);
// cout<<x.f<<" "<<x.s<<endl;
if (x.f == -1) {
lst = -1;
} else {
reverse(suf.begin(), suf.end());
lst = find1(suf);
// cout<<lst<<endl;
}
queries.pb({lst,{x.f, x.s}});
que.pb({x.s,lst});
que.pb({x.f - 1, lst});
// cout<<"gam"<<endl;
}
sort(que.begin(),que.end());
for (int i = 0; i < que.size(); i++) {
while(curi < que[i].f) {
curi++;
// cout<<in[endd[curi]]<<endl;
update(in[endd[curi]],1);
}
//idd = end[que[i].s];
if (que[i].s == -1) continue;
pas[que[i].s][que[i].f] = getans(out[que[i].s]) - getans(in[que[i].s] - 1);
}
int vert,lee,rii;
for (int i = 0; i < queries.size(); i++) {
vert = queries[i].f;
lee = queries[i].s.f; rii = queries[i].s.s;
if (vert == -1) cout<<0<<endl;
else
cout<<pas[vert][rii] - pas[vert][lee - 1]<<endl;
}
}
Compilation message
selling_rna.cpp: In function 'void dfs(int, int)':
selling_rna.cpp:30:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i = 0; i < v[a].size(); i++) {
| ~~^~~~~~~~~~~~~
selling_rna.cpp: In function 'void insert(std::string, int, int)':
selling_rna.cpp:39:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
selling_rna.cpp: In function 'std::pair<int, int> find(std::string)':
selling_rna.cpp:59:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i = 0; i < s1.size(); i++) {
| ~~^~~~~~~~~~~
selling_rna.cpp: In function 'int find1(std::string)':
selling_rna.cpp:67:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int i = 0; i < s1.size(); i++) {
| ~~^~~~~~~~~~~
selling_rna.cpp: In function 'std::string get(std::string)':
selling_rna.cpp:74:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i = 0; i < ss.size(); i++) {
| ~~^~~~~~~~~~~
selling_rna.cpp: At global scope:
selling_rna.cpp:82:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
82 | main() {
| ^~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:118:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for (int i = 0; i < que.size(); i++) {
| ~~^~~~~~~~~~~~
selling_rna.cpp:129:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for (int i = 0; i < queries.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
309 ms |
634444 KB |
Output is correct |
| 2 |
Correct |
302 ms |
634384 KB |
Output is correct |
| 3 |
Incorrect |
302 ms |
634456 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
545 ms |
750800 KB |
Output is correct |
| 2 |
Correct |
522 ms |
746244 KB |
Output is correct |
| 3 |
Incorrect |
391 ms |
675320 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
390 ms |
636536 KB |
Output is correct |
| 2 |
Correct |
359 ms |
635956 KB |
Output is correct |
| 3 |
Correct |
393 ms |
636132 KB |
Output is correct |
| 4 |
Correct |
359 ms |
636008 KB |
Output is correct |
| 5 |
Correct |
363 ms |
635712 KB |
Output is correct |
| 6 |
Correct |
414 ms |
636164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
309 ms |
634444 KB |
Output is correct |
| 2 |
Correct |
302 ms |
634384 KB |
Output is correct |
| 3 |
Incorrect |
302 ms |
634456 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
