#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e6;
char T[MAXN+10];
int N, M;
vector<int> A[MAXN+10];
int X[MAXN+10], Y[MAXN+10];
struct Node
{
int L, R;
Node *chd[4];
Node() : L(MAXN*2), R(0)
{
chd[0]=NULL; chd[1]=NULL; chd[2]=NULL; chd[3]=NULL;
}
};
void update(Node *node, vector<int> &V, int it)
{
if(it==V.size()) return;
if(node->chd[V[it]]==NULL) node->chd[V[it]]=new Node();
update(node->chd[V[it]], V, it+1);
}
int cnt=0;
void dfs(Node *node)
{
int i, j;
bool flag=true;
for(i=0; i<4; i++)
{
if(node->chd[i]==NULL) continue;
flag=false;
dfs(node->chd[i]);
node->L=min(node->L, node->chd[i]->L);
node->R=max(node->R, node->chd[i]->R);
}
if(flag) node->L=node->R=++cnt;
}
pii query(Node *node, vector<int> &V, int it)
{
if(it==V.size()) return {node->L, node->R};
if(node->chd[V[it]]==NULL) return {-1, -1};
return query(node->chd[V[it]], V, it+1);
}
Node *root1, *root2;
struct Data
{
int x, y1, y2, p;
bool operator < (const Data &p) { return x<p.x; }
};
vector<Data> DV;
struct BIT
{
vector<int> tree;
BIT() : tree(MAXN+10) {}
void update(int i) { for(; i<=N; i+=(i&-i)) tree[i]++; }
int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
int query(int l, int r) { return query(r)-query(l-1); }
}bit;
int ans[MAXN+10];
int main()
{
int i, j, k;
scanf("%d%d", &N, &M);
root1=new Node();
root2=new Node();
for(i=1; i<=N; i++)
{
scanf("%s", T);
for(j=0; T[j]; j++)
{
if(T[j]=='A') A[i].push_back(0);
if(T[j]=='G') A[i].push_back(1);
if(T[j]=='C') A[i].push_back(2);
if(T[j]=='U') A[i].push_back(3);
}
update(root1, A[i], 0);
reverse(A[i].begin(), A[i].end());
update(root2, A[i], 0);
reverse(A[i].begin(), A[i].end());
}
cnt=0;
dfs(root1);
for(i=1; i<=N; i++)
{
pii t=query(root1, A[i], 0);
X[i]=t.first;
}
cnt=0;
dfs(root2);
for(i=1; i<=N; i++)
{
reverse(A[i].begin(), A[i].end());
pii t=query(root2, A[i], 0);
reverse(A[i].begin(), A[i].end());
Y[i]=t.first;
}
vector<pii> PV;
for(i=1; i<=N; i++) PV.push_back({X[i], Y[i]});
for(i=1; i<=M; i++)
{
vector<int> B, C;
scanf("%s", T);
for(j=0; T[j]; j++)
{
if(T[j]=='A') B.push_back(0);
if(T[j]=='G') B.push_back(1);
if(T[j]=='C') B.push_back(2);
if(T[j]=='U') B.push_back(3);
}
scanf("%s", T);
for(j=0; T[j]; j++)
{
if(T[j]=='A') C.push_back(0);
if(T[j]=='G') C.push_back(1);
if(T[j]=='C') C.push_back(2);
if(T[j]=='U') C.push_back(3);
}
reverse(C.begin(), C.end());
pii xr=query(root1, B, 0), yr=query(root2, C, 0);
if(xr.first==-1 || yr.first==-1) continue;
DV.push_back({xr.first-1, yr.first, yr.second, -i});
DV.push_back({xr.second, yr.first, yr.second, i});
}
sort(DV.begin(), DV.end());
sort(PV.begin(), PV.end());
for(i=0, j=0, k=0; i<=N; i++)
{
for(; j<PV.size() && PV[j].first==i; j++) bit.update(PV[j].second);
for(; k<DV.size() && DV[k].x==i; k++)
{
int t=bit.query(DV[k].y1, DV[k].y2);
if(DV[k].p>0) ans[DV[k].p]+=t;
else ans[-DV[k].p]-=t;
}
}
for(i=1; i<=M; i++) printf("%d\n", ans[i]);
}
Compilation message
selling_rna.cpp: In function 'void update(Node*, std::vector<int>&, int)':
selling_rna.cpp:28:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(it==V.size()) return;
~~^~~~~~~~~~
selling_rna.cpp: In function 'void dfs(Node*)':
selling_rna.cpp:36:9: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
selling_rna.cpp: In function 'pii query(Node*, std::vector<int>&, int)':
selling_rna.cpp:51:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(it==V.size()) return {node->L, node->R};
~~^~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:153:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; j<PV.size() && PV[j].first==i; j++) bit.update(PV[j].second);
~^~~~~~~~~~
selling_rna.cpp:154:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; k<DV.size() && DV[k].x==i; k++)
~^~~~~~~~~~
selling_rna.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
selling_rna.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", T);
~~~~~^~~~~~~~~
selling_rna.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", T);
~~~~~^~~~~~~~~
selling_rna.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", T);
~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
55160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
244 ms |
158584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
59760 KB |
Output is correct |
| 2 |
Incorrect |
75 ms |
58732 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
55160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
