#include "dna.h"
#include <vector>
#include <iostream>
using namespace std;
vector<vector<int>> st;
int k;
void addv(vector<int>& re, vector<int> a) {
for (int i = 0; i < 6; i++) re[i] += a[i];
}
vector<int> range(int x, int y) {
vector<int> re(6, 0);
x += k; y += k;
while (x <= y) {
if (x % 2) addv(re, st[x++]);
if (!(y % 2)) addv(re, st[y--]);
x /= 2; y /= 2;
}
return re;
}
int calculate_ans(vector<int> a) {
if (a[0] - a[3] == a[1] - a[4] && a[1] - a[4] == a[2] - a[5]) {
int ans;
if (a[0] < a[3]) {
ans = a[0] + a[1] + a[2] + 2 * (a[3] - a[0]);
}
else {
ans = a[3] + a[4] + a[5] + 2 * (a[0] - a[3]);
}
return ans;
}
return -1;
}
void init(string a, string b) {
int n = a.size();
k = 1;
while (k < n) k *= 2;
st.resize(2*k, vector<int>(6, 0));
for (int i = 0; i < n; i++) {
if (a[i] == 'A') {
if (b[i] == 'C') {
st[i + k][0] = 1;
}
else if (b[i] == 'T') {
st[i + k][5] = 1;
}
}
else if (a[i] == 'C') {
if (b[i] == 'A') {
st[i + k][3] = 1;
}
else if (b[i] == 'T') {
st[i + k][1] = 1;
}
}
else {
if (b[i] == 'A') {
st[i + k][2] = 1;
}
else if (b[i] == 'C') {
st[i + k][4] = 1;
}
}
}
for (int i = k - 1; i > 0; i--) {
for (int j = 0; j < 6; j++) {
st[i][j] += st[2*i][j];
st[i][j] += st[2*i+1][j];
}
}
// for (int i = 1; i < 2 * k; i++) {
// cout << "[";
// for (int j = 0; j < 5; j++) {
// cout << st[i][j] << ", ";
// }
// cout << st[i][5] << "]\n";
// }
}
int get_distance(int x, int y) {
vector<int> use = range(x, y);
return calculate_ans(use);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
60 ms |
17868 KB |
Output is correct |
2 |
Correct |
61 ms |
17876 KB |
Output is correct |
3 |
Correct |
60 ms |
17804 KB |
Output is correct |
4 |
Correct |
59 ms |
17980 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
304 KB |
Output is correct |
4 |
Correct |
18 ms |
15408 KB |
Output is correct |
5 |
Correct |
18 ms |
15416 KB |
Output is correct |
6 |
Correct |
18 ms |
15416 KB |
Output is correct |
7 |
Correct |
18 ms |
15316 KB |
Output is correct |
8 |
Correct |
19 ms |
15416 KB |
Output is correct |
9 |
Correct |
21 ms |
15360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
304 KB |
Output is correct |
4 |
Correct |
18 ms |
15408 KB |
Output is correct |
5 |
Correct |
18 ms |
15416 KB |
Output is correct |
6 |
Correct |
18 ms |
15416 KB |
Output is correct |
7 |
Correct |
18 ms |
15316 KB |
Output is correct |
8 |
Correct |
19 ms |
15416 KB |
Output is correct |
9 |
Correct |
21 ms |
15360 KB |
Output is correct |
10 |
Correct |
63 ms |
17896 KB |
Output is correct |
11 |
Correct |
61 ms |
17916 KB |
Output is correct |
12 |
Correct |
134 ms |
18196 KB |
Output is correct |
13 |
Correct |
122 ms |
18276 KB |
Output is correct |
14 |
Correct |
124 ms |
18268 KB |
Output is correct |
15 |
Correct |
121 ms |
18232 KB |
Output is correct |
16 |
Correct |
121 ms |
18116 KB |
Output is correct |
17 |
Correct |
139 ms |
18152 KB |
Output is correct |
18 |
Correct |
119 ms |
18212 KB |
Output is correct |
19 |
Correct |
114 ms |
18096 KB |
Output is correct |
20 |
Correct |
133 ms |
18132 KB |
Output is correct |
21 |
Correct |
104 ms |
18232 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
304 KB |
Output is correct |
4 |
Correct |
18 ms |
15408 KB |
Output is correct |
5 |
Correct |
18 ms |
15416 KB |
Output is correct |
6 |
Correct |
18 ms |
15416 KB |
Output is correct |
7 |
Correct |
18 ms |
15316 KB |
Output is correct |
8 |
Correct |
19 ms |
15416 KB |
Output is correct |
9 |
Correct |
21 ms |
15360 KB |
Output is correct |
10 |
Correct |
19 ms |
15316 KB |
Output is correct |
11 |
Correct |
18 ms |
15444 KB |
Output is correct |
12 |
Correct |
23 ms |
15344 KB |
Output is correct |
13 |
Correct |
19 ms |
15408 KB |
Output is correct |
14 |
Correct |
18 ms |
15416 KB |
Output is correct |
15 |
Correct |
17 ms |
15444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
60 ms |
17868 KB |
Output is correct |
2 |
Correct |
61 ms |
17876 KB |
Output is correct |
3 |
Correct |
60 ms |
17804 KB |
Output is correct |
4 |
Correct |
59 ms |
17980 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
304 KB |
Output is correct |
11 |
Correct |
18 ms |
15408 KB |
Output is correct |
12 |
Correct |
18 ms |
15416 KB |
Output is correct |
13 |
Correct |
18 ms |
15416 KB |
Output is correct |
14 |
Correct |
18 ms |
15316 KB |
Output is correct |
15 |
Correct |
19 ms |
15416 KB |
Output is correct |
16 |
Correct |
21 ms |
15360 KB |
Output is correct |
17 |
Correct |
63 ms |
17896 KB |
Output is correct |
18 |
Correct |
61 ms |
17916 KB |
Output is correct |
19 |
Correct |
134 ms |
18196 KB |
Output is correct |
20 |
Correct |
122 ms |
18276 KB |
Output is correct |
21 |
Correct |
124 ms |
18268 KB |
Output is correct |
22 |
Correct |
121 ms |
18232 KB |
Output is correct |
23 |
Correct |
121 ms |
18116 KB |
Output is correct |
24 |
Correct |
139 ms |
18152 KB |
Output is correct |
25 |
Correct |
119 ms |
18212 KB |
Output is correct |
26 |
Correct |
114 ms |
18096 KB |
Output is correct |
27 |
Correct |
133 ms |
18132 KB |
Output is correct |
28 |
Correct |
104 ms |
18232 KB |
Output is correct |
29 |
Correct |
19 ms |
15316 KB |
Output is correct |
30 |
Correct |
18 ms |
15444 KB |
Output is correct |
31 |
Correct |
23 ms |
15344 KB |
Output is correct |
32 |
Correct |
19 ms |
15408 KB |
Output is correct |
33 |
Correct |
18 ms |
15416 KB |
Output is correct |
34 |
Correct |
17 ms |
15444 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
58 ms |
17868 KB |
Output is correct |
37 |
Correct |
63 ms |
17924 KB |
Output is correct |
38 |
Correct |
139 ms |
18224 KB |
Output is correct |
39 |
Correct |
127 ms |
18272 KB |
Output is correct |
40 |
Correct |
136 ms |
18284 KB |
Output is correct |
41 |
Correct |
22 ms |
15392 KB |
Output is correct |
42 |
Correct |
115 ms |
18140 KB |
Output is correct |
43 |
Correct |
125 ms |
18192 KB |
Output is correct |
44 |
Correct |
143 ms |
18208 KB |
Output is correct |
45 |
Correct |
106 ms |
18120 KB |
Output is correct |
46 |
Correct |
104 ms |
18172 KB |
Output is correct |
47 |
Correct |
103 ms |
18192 KB |
Output is correct |