#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int SIZEMAX = 2000005;
const int INF = 1000000005;
struct Node {
int mn, mx, nxt[4];
Node() : mn(INF), mx(-INF) {
memset(nxt, 0, sizeof nxt); } };
struct Event {
int typ; pair<int, int> seg;
Event(int _typ, pair<int, int> _seg) :
typ(_typ), seg(_seg) {} };
string str[MAXN], rev[MAXN];
Node trie1[SIZEMAX], trie2[SIZEMAX];
vector<Event> evn[MAXN];
pair<int, int> sgx[MAXN], sgy[MAXN];
int bit[MAXN], ans[MAXN];
void insert(Node trie[], int &tot, int nd, int ps, string &str) {
if (ps != str.length()) {
if (!trie[nd].nxt[str[ps]]) {
trie[nd].nxt[str[ps]] = ++tot; }
insert(trie, tot, trie[nd].nxt[str[ps]], ps + 1, str); } }
void dfs(Node trie[], int &tot, int nd) {
for (int i = 0; i < 4; ++i) {
if (trie[nd].nxt[i] != 0) {
dfs(trie, tot, trie[nd].nxt[i]);
trie[nd].mn = min(trie[nd].mn, trie[trie[nd].nxt[i]].mn);
trie[nd].mx = max(trie[nd].mx, trie[trie[nd].nxt[i]].mx); } }
if (trie[nd].mn == INF) {
trie[nd].mn = trie[nd].mx = ++tot; } }
int _mn, _mx;
void getMinMax(Node trie[], int nd, int ps, string &str) {
if (ps == str.length()) {
_mn = trie[nd].mn; _mx = trie[nd].mx; }
else {
if (!trie[nd].nxt[str[ps]]) {
_mn = INF; _mx = -INF; }
else {
getMinMax(trie, trie[nd].nxt[str[ps]], ps + 1, str); } } }
void changeString(string &str) {
for (char &ch : str) {
if (ch == 'A') { ch = 0; }
if (ch == 'C') { ch = 1; }
if (ch == 'G') { ch = 2; }
if (ch == 'U') { ch = 3; } } }
void update(int ps, int vl) {
for (; ps < MAXN; ps += (ps & -ps)) {
bit[ps] += vl; } }
int query(int ps, int vl = 0) {
for (; ps > 0; ps -= (ps & -ps)) {
vl += bit[ps]; }
return vl; }
int main(void) {
#ifdef HOME
freopen("sellrna.in", "r", stdin);
freopen("sellrna.out", "w", stdout);
#endif
int n, m; cin >> n >> m;
for (int i = 1, nr1 = 1, nr2 = 1; i <= n; ++i) {
cin >> str[i]; changeString(str[i]);
rev[i] = str[i]; reverse(rev[i].begin(), rev[i].end());
insert(trie1, nr1, 1, 0, str[i]); insert(trie2, nr2, 1, 0, rev[i]); }
int nr; nr = 0; dfs(trie1, nr, 1); nr = 0; dfs(trie2, nr, 1);
for (int i = 1; i <= n; ++i) {
_mn = INF; _mx = -INF; getMinMax(trie1, 1, 0, str[i]); int ps1 = _mn;
_mn = INF; _mx = -INF; getMinMax(trie2, 1, 0, rev[i]); int ps2 = _mn;
evn[ps1].push_back(Event(0, make_pair(ps2, ps2))); }
for (int i = 1; i <= m; ++i) {
string str1, str2; cin >> str1 >> str2;
changeString(str1); changeString(str2); reverse(str2.begin(), str2.end());
_mn = INF; _mx = -INF; getMinMax(trie1, 1, 0, str1); sgx[i] = make_pair(_mn, _mx);
_mn = INF; _mx = -INF; getMinMax(trie2, 1, 0, str2); sgy[i] = make_pair(_mn, _mx);
if (sgx[i].first != INF and sgy[i].first != INF) {
evn[sgx[i].first - 1].push_back(Event(-i, sgy[i]));
evn[sgx[i].second].push_back(Event(i, sgy[i])); } }
for (int i = 1; i <= n; ++i) {
for (auto &ev : evn[i]) {
if (ev.typ == 0) {
update(ev.seg.first, 1); }
else {
ans[abs(ev.typ)] += (query(ev.seg.second) - query(ev.seg.first - 1)) * (ev.typ < 0 ? -1 : 1); } } }
for (int i = 1; i <= m; ++i) {
cout << ans[i] << "\n"; }
return 0; }
Compilation message
selling_rna.cpp: In function 'void insert(Node*, int&, int, int, std::__cxx11::string&)':
selling_rna.cpp:26:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ps != str.length()) {
~~~^~~~~~~~~~~~~~~
selling_rna.cpp:27:28: warning: array subscript has type 'char' [-Wchar-subscripts]
if (!trie[nd].nxt[str[ps]]) {
^
selling_rna.cpp:28:24: warning: array subscript has type 'char' [-Wchar-subscripts]
trie[nd].nxt[str[ps]] = ++tot; }
^
selling_rna.cpp:29:41: warning: array subscript has type 'char' [-Wchar-subscripts]
insert(trie, tot, trie[nd].nxt[str[ps]], ps + 1, str); } }
^
selling_rna.cpp: In function 'void getMinMax(Node*, int, int, std::__cxx11::string&)':
selling_rna.cpp:42:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ps == str.length()) {
~~~^~~~~~~~~~~~~~~
selling_rna.cpp:45:28: warning: array subscript has type 'char' [-Wchar-subscripts]
if (!trie[nd].nxt[str[ps]]) {
^
selling_rna.cpp:48:40: warning: array subscript has type 'char' [-Wchar-subscripts]
getMinMax(trie, trie[nd].nxt[str[ps]], ps + 1, str); } } }
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
102904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
360 ms |
112256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
112256 KB |
Output is correct |
| 2 |
Incorrect |
123 ms |
112256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
102904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
