#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef pair <pii, pii> ppp;
const int INF=0x3f3f3f3f;
const int N=1e5+5;
const int MAX=2e6+5;
struct Node{
Node* CH[4];
int dt, kraj, rig;
Node() {
dt=0; kraj=0;
memset(CH, 0, sizeof CH);
}
};
int n, q, len, cnt=0;
char inp[N];
string s[N];
Node *root=new Node(), *root_r=new Node();
int sol[N];
vector <int> toc[N];
vector <ppp> v[N]; //((dole, gore), (index, +-1))
int F[N];
void update(int x, int val) {
for (x++; x<=n+1; x+=x&-x) F[x]+=val;
}
int query_(int x) {
int ret=0;
for (x++; x>0; x-=x&-x) ret+=F[x];
return ret;
}
int query(int l, int r) {
return query_(r-1)-query_(l-1);
}
void dodaj(Node *curr) {
for (int i=0; i<len; ++i) {
if (curr->CH[inp[i]-'A']==NULL) curr->CH[inp[i]-'A']=new Node();
curr=curr->CH[inp[i]-'A'];
}
curr->kraj=1;
}
void dfs(Node *curr) {
if (!curr) return;
curr->dt=cnt;
cnt+=curr->kraj;
for (int i=0; i<4; ++i) dfs(curr->CH[i]);
curr->rig=cnt;
}
pii interval(Node* curr) {
len=strlen(inp);
for (int i=0; i<len; ++i) {
curr=curr->CH[inp[i]-'A'];
if (!curr) return mp(0, 0);
}
return mp(curr->dt, curr->rig);
}
void convert() {
for (int i=0; i<len; ++i) {
if (inp[i]=='G') inp[i]='B';
if (inp[i]=='U') inp[i]='D';
}
}
void solve() {
dfs(root);
cnt=0;
dfs(root_r);
for (int i=0; i<q; ++i) {
scanf("%s", inp);
len=strlen(inp);
convert();
pii a=interval(root);
scanf("%s", inp); len=strlen(inp);
convert();
pii b=interval(root_r);
v[a.X].pb({b, {i, -1}});
v[a.Y].pb({b, {i, 1}});
}
for (int i=0; i<n; ++i) {
len=s[i].size();
for (int j=0; j<len; ++j) inp[j]=s[i][j];
inp[len]='\0';
// printf("string: %s\n", inp);
int x=interval(root).X;
reverse(inp, inp+len);
int y=interval(root_r).X;
toc[x].pb(y);
}
for (int i=0; i<=n+1; ++i) {
for (ppp pp:v[i]) sol[pp.Y.X]+=pp.Y.Y*query(pp.X.X, pp.X.Y);
for (int y:toc[i]) update(y, 1);
}
for (int i=0; i<q; ++i) printf("%d\n", sol[i]);
}
void load() {
scanf("%d %d", &n, &q);
for (int i=0; i<n; ++i) {
scanf("%s", inp);
len=strlen(inp);
convert();
s[i]=inp;
dodaj(root);
reverse(inp, inp+len);
dodaj(root_r);
}
}
int main() {
load();
solve();
return 0;
}
Compilation message
selling_rna.cpp: In function 'void solve()':
selling_rna.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
91 | scanf("%s", inp);
| ~~~~~^~~~~~~~~~~
selling_rna.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
96 | scanf("%s", inp); len=strlen(inp);
| ~~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'void load()':
selling_rna.cpp:124:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
124 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
126 | scanf("%s", inp);
| ~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
8172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
243 ms |
137964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
10916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
8172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
