#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#define DIM 100005
using namespace std;
int n, m, k, i, j, u, ii;
int ind[DIM], sol[DIM];
char p[DIM], q[DIM];
vector<char> v[DIM], c[DIM];
struct str{
int p, u, ind;
};
str w[DIM];
struct trie1{
int minim, maxim;
trie1 *f[5];
trie1(){
minim = 10000000;
maxim = 0;
f[4] = f[1] = f[2] = f[3] = NULL;
}
};
trie1 *r1;
struct trie2{
vector<int> v;
trie2 *f[5];
trie2(){
f[4] = f[1] = f[2] = f[3] = NULL;
}
};
trie2 *r2;
void read(char s[]){
cin>> s;
k = strlen(s);
for(int i = 0; i < k; i++){
if(s[i] == 'A'){
s[i] = 1;
}
if(s[i] == 'C'){
s[i] = 2;
}
if(s[i] == 'G'){
s[i] = 3;
}
if(s[i] == 'U'){
s[i] = 4;
}
}
}
int cmp2(str a, str b){
return a.p > b.p;
}
int cmp(int a, int b){
for(int i = 0; i < min(v[a].size(), v[b].size() ); i++){
if(v[a][i] != v[b][i]){
return v[a][i] < v[b][i];
}
}
return v[a].size() < v[b].size();
}
void adauga1(trie1 *r, char *s, int ind){
r->minim = min(r->minim, ind);
r->maxim = max(r->maxim, ind);
if(*s != 0){
if(r->f[*s] == NULL){
r->f[*s] = new trie1;
}
adauga1(r->f[*s], s + 1, ind);
}
}
void query1(trie1 *r, char *s, str &w){
if(*s == 0){
w.p = r->minim;
w.u = r->maxim;
}
else{
if(r->f[*s] != NULL){
query1(r->f[*s], s + 1, w);
}
}
}
void adauga2(trie2 *r, char *s, int ind){
r->v.push_back(ind);
if(*s != 0){
if(r->f[*s] == NULL){
r->f[*s] = new trie2;
}
adauga2(r->f[*s], s + 1, ind);
}
}
int query2(trie2 *r, char *s, int ind){
if(*s == 0){
int st, dr, mid;
st = 0;
dr = r->v.size() - 1;
while(st <= dr){
mid = (st + dr) / 2;
if(r->v[mid] <= ind){
st = mid + 1;
}
else{
dr = mid - 1;
}
}
return dr + 1;
}
if(r->f[*s] == NULL){
return 0;
}
return query2(r->f[*s], s + 1, ind);
}
void copiere(vector<char> v){
for(int i = 0; i < v.size(); i++){
p[i] = v[i];
}
p[i] = 0;
}
int main(){
r1 = new trie1;
r2 = new trie2;
cin>> n >> m;
for(i = 1; i <= n; i++){
read(p);
ind[i] = i;
for(j = 0; j < k; j++){
v[i].push_back(p[j]);
}
}
sort(ind + 1, ind + n + 1, cmp);
for(i = 1; i <= n; i++){
copiere(v[ ind[i] ]);
adauga1(r1, p, ind[i]);
}
for(i = 1; i <= m; i++){
read(p);
w[i].ind = i;
w[i].p = 1000000;
query1(r1, p, w[i]);
read(q);
for(j = 0; j < k; j++){
c[i].push_back(q[j]);
}
}
sort(w + 1, w + m + 1, cmp2);
u = 1;
for(ii = 1; ii <= n; ii++){
for(i = 0, j = v[ii].size() - 1; i < j; i++, j--){
swap(v[ii][i], v[ii][j]);
}
}
while(w[u].p > n){
u++;
}
for(i = n; i >= 1; i--){
copiere(v[ ind[i] ]);
adauga2(r2, p, ind[i]);
while(w[u].p == i){
copiere(c[ w[u].ind ]);
sol[ w[u].ind ] = query2(r2, p, w[u].u);
u++;
}
}
for(i = 1; i <= m; i++){
cout<< sol[i] <<"\n";
}
}
Compilation message
selling_rna.cpp: In function 'int cmp(int, int)':
selling_rna.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
55 | for(int i = 0; i < min(v[a].size(), v[b].size() ); i++){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp: In function 'void adauga1(trie1*, char*, int)':
selling_rna.cpp:66:17: warning: array subscript has type 'char' [-Wchar-subscripts]
66 | if(r->f[*s] == NULL){
| ^~
selling_rna.cpp:67:18: warning: array subscript has type 'char' [-Wchar-subscripts]
67 | r->f[*s] = new trie1;
| ^~
selling_rna.cpp:69:22: warning: array subscript has type 'char' [-Wchar-subscripts]
69 | adauga1(r->f[*s], s + 1, ind);
| ^~
selling_rna.cpp: In function 'void query1(trie1*, char*, str&)':
selling_rna.cpp:78:17: warning: array subscript has type 'char' [-Wchar-subscripts]
78 | if(r->f[*s] != NULL){
| ^~
selling_rna.cpp:79:25: warning: array subscript has type 'char' [-Wchar-subscripts]
79 | query1(r->f[*s], s + 1, w);
| ^~
selling_rna.cpp: In function 'void adauga2(trie2*, char*, int)':
selling_rna.cpp:86:17: warning: array subscript has type 'char' [-Wchar-subscripts]
86 | if(r->f[*s] == NULL){
| ^~
selling_rna.cpp:87:18: warning: array subscript has type 'char' [-Wchar-subscripts]
87 | r->f[*s] = new trie2;
| ^~
selling_rna.cpp:89:22: warning: array subscript has type 'char' [-Wchar-subscripts]
89 | adauga2(r->f[*s], s + 1, ind);
| ^~
selling_rna.cpp: In function 'int query2(trie2*, char*, int)':
selling_rna.cpp:108:13: warning: array subscript has type 'char' [-Wchar-subscripts]
108 | if(r->f[*s] == NULL){
| ^~
selling_rna.cpp:111:24: warning: array subscript has type 'char' [-Wchar-subscripts]
111 | return query2(r->f[*s], s + 1, ind);
| ^~
selling_rna.cpp: In function 'void copiere(std::vector<char>)':
selling_rna.cpp:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
464 ms |
175676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
10740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
