#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXSZ = 1e5+1;
const int LIM = 1e6+1;
int trans(char a) {
if (a == 'A') return 0;
else if (a == 'U') return 1;
else if (a == 'C') return 2;
else if (a == 'G') return 3;
else return -1;
}
int N, M;
pii l[2][MAXSZ], r[2][MAXSZ];
struct node {
vector<pii> end;
node* nxt[4];
node() {nxt[0] = nxt[1] = nxt[2] = nxt[3] = 0;}
void insert(char s[], pii p) {
int x = trans(*s);
if (x == -1)
end.push_back(p);
else {
if (!nxt[x]) nxt[x] = new node();
nxt[x]->insert(s+1, p);
}
}
int dfs(pii to[2][MAXSZ], int t = 0) {
printf("dfs t %d: ", t);
for (pii p : end) printf("%d,%d ", p.first, p.second);
printf("\n");
if (!end.empty()) {
++t;
for (pii p : end)
to[p.first][p.second].first = t;
}
for (int i = 0; i < 4; i++)
if (nxt[i]) t = nxt[i]->dfs(to, t);
for (pii p : end)
to[p.first][p.second].second = t;
return t;
}
};
struct bit {
int sz;
vector<int> v;
bit (int sz) : sz(sz), v(sz+1, 0) {};
void upd(int x, int d) {while (x < sz) v[x]+=d, x += x&-x;}
int query(int x) {int ret=0; while (x) ret+=v[x], x -= x&-x; return ret;}
} bb(2*MAXSZ);
enum type { pBegin = 1, tBegin = 2, pEnd = 3, tEnd = 4 };
struct event {
type t;
int pos;
int i;
event(type t, int pos, int i) : t(t), pos(pos), i(i) {};
bool operator<(event& o) {
if (this->pos != o.pos) return this->pos < o.pos;
else return this->t < o.t;
}
};
int ans[MAXSZ];
int main()
{
char buf[LIM];
node* treeL = new node(), * treeR = new node();
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++) {
scanf("%s", &buf);
int sz = strlen(buf);
treeL->insert(buf, pii(0,i));
reverse(buf, buf+sz);
treeR->insert(buf, pii(0,i));
}
for (int i = 0; i < M; i++) {
scanf("%s", &buf);
treeL->insert(buf, pii(1,i));
scanf("%s", &buf);
int sz = strlen(buf);
reverse(buf, buf+sz);
treeR->insert(buf, pii(1,i));
}
treeL->dfs(l);
treeR->dfs(r);
vector<event> ev;
for (int i = 0; i < N; i++)
ev.push_back(event(tBegin, l[0][i].first, i));
for (int i = 0; i < M; i++) {
ev.push_back(event(pBegin, l[1][i].first, i));
ev.push_back(event(pEnd, l[1][i].second, i));
}
sort(ev.begin(), ev.end());
for (event p : ev) {
if (p.t == pBegin)
ans[p.i] -= bb.query(r[1][p.i].second) - bb.query(r[1][p.i].first-1);
else if (p.t == pEnd)
ans[p.i] += bb.query(r[1][p.i].second) - bb.query(r[1][p.i].first-1);
else if (p.t == tBegin)
bb.upd(r[0][p.i].first, 1);
else
bb.upd(r[0][p.i].first, -1);
}
for (int i = 0; i < M; i++) printf("%d\n", ans[i]);
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:85:19: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1000001]' [-Wformat=]
scanf("%s", &buf);
^
selling_rna.cpp:93:19: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1000001]' [-Wformat=]
scanf("%s", &buf);
^
selling_rna.cpp:96:20: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[1000001]' [-Wformat=]
scanf("%s", &buf);
^
selling_rna.cpp:82:24: 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:85:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", &buf);
^
selling_rna.cpp:93:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", &buf);
^
selling_rna.cpp:96:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", &buf);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
7180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
583 ms |
130956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
14392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
7180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
