//Sasayego! Sasayego! Shinzou wo Sasageyo!
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bitset>
#include <ctime>
#define debug(x) cerr << #x << " = " << x << endl
#define lid (id << 1)
#define rid (lid ^ 1)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
const int maxN = 1e5 + 5;
const int maxM = 2e6 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
map <char, int> MAPPA;
int trie[maxM][4], num[maxN], ans[maxN];
int st[maxM], fn[maxM], TIME = 0;
pii pos[maxN];
vector <pii> quer[maxN];
string s[maxN], pre[maxN], suf[maxN];
void getstr(string& S, char C = '\n'){
char ch;
while ((ch = getchar()) != C)
S += ch;
return;
}
void LEVI(int v = 0){
st[v] = TIME++;
for (int i = 0; i < 4; i++)
if (trie[v][i] != -1)
LEVI(trie[v][i]);
fn[v] = TIME;
return;
}
int main(){
time_t START = clock();
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
memset(trie, -1, sizeof trie);
MAPPA['A'] = 0;
MAPPA['C'] = 1;
MAPPA['G'] = 2;
MAPPA['U'] = 3;
int n, q; scanf("%d%d\n", &n, &q);
for (int i = 0; i < n; i++)
getstr(s[i]);
int N = 0, curr;
for (int i = 0; i < n; i++){
curr = 0;
for (char ch : s[i]){
int c = MAPPA[ch];
if (trie[curr][c] == -1)
trie[curr][c] = ++N;
curr = trie[curr][c];
}
num[i] = curr;
}
LEVI();
for (int i = 0; i < n; i++)
pos[i] = {st[num[i]], i};
sort(pos, pos + n);
for (int i = 0; i < q; i++){
getstr(pre[i], ' ');
getstr(suf[i]);
reverse(suf[i].begin(), suf[i].end());
curr = 0;
for (char ch : pre[i]){
if (curr == -1)
break;
curr = trie[curr][MAPPA[ch]];
}
if (curr > 0){
int l = lower_bound(pos, pos + n, make_pair(st[curr], 0)) - pos;
int r = lower_bound(pos, pos + n, make_pair(fn[curr], 0)) - pos;
quer[l].push_back({-1, i});
quer[r].push_back({+1, i});
}
}
for (int i = 0; i < n; i++)
reverse(s[i].begin(), s[i].end());
memset(trie, -1, sizeof trie);
memset(num, 0, sizeof num);
N = 0;
for (int i = 0; i <= n; i++){
for (pii pp : quer[i]){
int id, tmp; tie(tmp, id) = pp;
curr = 0;
for (char ch : suf[id]){
if (curr == -1)
break;
curr = trie[curr][MAPPA[ch]];
}
if (curr > 0)
ans[id] += tmp * num[curr];
}
if (i < n){
curr = 0;
for (char ch : s[pos[i].second]){
int c = MAPPA[ch];
if (trie[curr][c] == -1)
trie[curr][c] = ++N;
curr = trie[curr][c];
num[curr]++;
}
}
}
for (int i = 0; i < q; i++)
printf("%d\n", ans[i]);
time_t FINISH = clock();
cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " milliseconds.\n";
return 0;
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:63:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n, q; scanf("%d%d\n", &n, &q);
~~~~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
43776 KB |
Output is correct |
2 |
Correct |
28 ms |
43904 KB |
Output is correct |
3 |
Correct |
27 ms |
43896 KB |
Output is correct |
4 |
Correct |
28 ms |
43776 KB |
Output is correct |
5 |
Correct |
28 ms |
43776 KB |
Output is correct |
6 |
Correct |
28 ms |
43776 KB |
Output is correct |
7 |
Correct |
27 ms |
43776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
193 ms |
53752 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
46296 KB |
Output is correct |
2 |
Correct |
49 ms |
45616 KB |
Output is correct |
3 |
Correct |
58 ms |
45812 KB |
Output is correct |
4 |
Correct |
47 ms |
45560 KB |
Output is correct |
5 |
Correct |
51 ms |
45432 KB |
Output is correct |
6 |
Correct |
55 ms |
45688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
43776 KB |
Output is correct |
2 |
Correct |
28 ms |
43904 KB |
Output is correct |
3 |
Correct |
27 ms |
43896 KB |
Output is correct |
4 |
Correct |
28 ms |
43776 KB |
Output is correct |
5 |
Correct |
28 ms |
43776 KB |
Output is correct |
6 |
Correct |
28 ms |
43776 KB |
Output is correct |
7 |
Correct |
27 ms |
43776 KB |
Output is correct |
8 |
Incorrect |
193 ms |
53752 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |