#include<bits/stdc++.h>
#include "dna.h"
using namespace std;
int minSwaps(array<array<int, 3>, 3> a){
int res = 0;
int x = min(a[0][1], a[1][0]);
res += x;
a[0][1] -= x;
a[1][0] -= x;
x = min(a[0][2], a[2][0]);
res += x;
a[0][2] -= x;
a[2][0] -= x;
x = min(a[1][2], a[2][1]);
res += x;
a[1][2] -= x;
a[2][1] -= x;
if(a[0][1] + a[0][2] != a[1][0] + a[2][0] || a[1][0] + a[1][2] != a[0][1] + a[0][2] || a[2][0] + a[2][1] != a[0][2] + a[1][2])return -1;
res += 2 * (a[0][1] + a[0][2] + a[1][0] + a[1][2] + a[2][0] + a[2][1])/3;
return res;
}
class Tree{
private:
int lrSize = 2;
vector<array<array<int, 3>, 3>> v;
void update(int pos){
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
v[pos][i][j] = v[2*pos][i][j] + v[2*pos + 1][i][j];
}
}
}
void rangeSum(int a, int b, int l, int r, int pos, array<array<int,3>, 3>& ans){
if(b < l || r < a)return;
if(a <= l && r <= b){
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++)ans[i][j] += v[pos][i][j];
}
}else{
int m = (l + r)/2;
rangeSum(a, b, l, m, 2*pos, ans);
rangeSum(a, b, m+1, r, 2*pos+1, ans);
}
}
public:
void init(string a, string b){
int n = a.length();
while(lrSize < n)lrSize *= 2;
v.resize(2*lrSize);
for(int i = 0; i < lrSize; i++){
for(int j = 0; j < 3; j++){
for(int k = 0; k < 3; k++){
v[lrSize + i][j][k] = 0;
}
}
int x, y;
if(a[i] == 'A') x = 0;
else if(a[i] == 'T')x=1;
else x = 2;
if(b[i] == 'A') y = 0;
else if(b[i] == 'T')y=1;
else y = 2;
if(i < n){
v[lrSize+i][x][y] = 1;
}
}
for(int i = lrSize - 1; i >= 1; i--)update(i);
}
Tree(){
}
int getAns(int a, int b){
array<array<int, 3>, 3> ans;
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++)ans[i][j] = 0;
}
rangeSum(a, b, 0, lrSize-1, 1, ans);
return minSwaps(ans);
}
};
Tree tree;
void init(string a, string b){
tree.init(a, b);
}
int get_distance(int x, int y){
return tree.getAns(x, y);
}
/*
int main(){
int n, q; cin>>n>>q;
string a, b; cin>>a>>b;
init(a, b);
for(int i = 0; i < q; i++){
int x, y; cin>>x>>y;
cout<<get_distance(x, y)<<"\n";
}
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
12840 KB |
Output is correct |
2 |
Correct |
57 ms |
12728 KB |
Output is correct |
3 |
Correct |
54 ms |
12620 KB |
Output is correct |
4 |
Correct |
57 ms |
12748 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
13 ms |
10524 KB |
Output is correct |
5 |
Correct |
13 ms |
10452 KB |
Output is correct |
6 |
Correct |
13 ms |
10488 KB |
Output is correct |
7 |
Correct |
14 ms |
10444 KB |
Output is correct |
8 |
Correct |
15 ms |
10452 KB |
Output is correct |
9 |
Correct |
14 ms |
10452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
13 ms |
10524 KB |
Output is correct |
5 |
Correct |
13 ms |
10452 KB |
Output is correct |
6 |
Correct |
13 ms |
10488 KB |
Output is correct |
7 |
Correct |
14 ms |
10444 KB |
Output is correct |
8 |
Correct |
15 ms |
10452 KB |
Output is correct |
9 |
Correct |
14 ms |
10452 KB |
Output is correct |
10 |
Correct |
68 ms |
12820 KB |
Output is correct |
11 |
Correct |
57 ms |
12732 KB |
Output is correct |
12 |
Correct |
88 ms |
13016 KB |
Output is correct |
13 |
Correct |
113 ms |
13048 KB |
Output is correct |
14 |
Correct |
117 ms |
13104 KB |
Output is correct |
15 |
Correct |
115 ms |
12948 KB |
Output is correct |
16 |
Correct |
92 ms |
12932 KB |
Output is correct |
17 |
Correct |
85 ms |
12976 KB |
Output is correct |
18 |
Correct |
121 ms |
12992 KB |
Output is correct |
19 |
Correct |
74 ms |
12952 KB |
Output is correct |
20 |
Correct |
74 ms |
12984 KB |
Output is correct |
21 |
Correct |
111 ms |
12968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
13 ms |
10524 KB |
Output is correct |
5 |
Correct |
13 ms |
10452 KB |
Output is correct |
6 |
Correct |
13 ms |
10488 KB |
Output is correct |
7 |
Correct |
14 ms |
10444 KB |
Output is correct |
8 |
Correct |
15 ms |
10452 KB |
Output is correct |
9 |
Correct |
14 ms |
10452 KB |
Output is correct |
10 |
Correct |
13 ms |
10424 KB |
Output is correct |
11 |
Correct |
15 ms |
10452 KB |
Output is correct |
12 |
Correct |
14 ms |
10428 KB |
Output is correct |
13 |
Correct |
16 ms |
10452 KB |
Output is correct |
14 |
Correct |
14 ms |
10452 KB |
Output is correct |
15 |
Correct |
16 ms |
10428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
12840 KB |
Output is correct |
2 |
Correct |
57 ms |
12728 KB |
Output is correct |
3 |
Correct |
54 ms |
12620 KB |
Output is correct |
4 |
Correct |
57 ms |
12748 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
13 ms |
10524 KB |
Output is correct |
12 |
Correct |
13 ms |
10452 KB |
Output is correct |
13 |
Correct |
13 ms |
10488 KB |
Output is correct |
14 |
Correct |
14 ms |
10444 KB |
Output is correct |
15 |
Correct |
15 ms |
10452 KB |
Output is correct |
16 |
Correct |
14 ms |
10452 KB |
Output is correct |
17 |
Correct |
68 ms |
12820 KB |
Output is correct |
18 |
Correct |
57 ms |
12732 KB |
Output is correct |
19 |
Correct |
88 ms |
13016 KB |
Output is correct |
20 |
Correct |
113 ms |
13048 KB |
Output is correct |
21 |
Correct |
117 ms |
13104 KB |
Output is correct |
22 |
Correct |
115 ms |
12948 KB |
Output is correct |
23 |
Correct |
92 ms |
12932 KB |
Output is correct |
24 |
Correct |
85 ms |
12976 KB |
Output is correct |
25 |
Correct |
121 ms |
12992 KB |
Output is correct |
26 |
Correct |
74 ms |
12952 KB |
Output is correct |
27 |
Correct |
74 ms |
12984 KB |
Output is correct |
28 |
Correct |
111 ms |
12968 KB |
Output is correct |
29 |
Correct |
13 ms |
10424 KB |
Output is correct |
30 |
Correct |
15 ms |
10452 KB |
Output is correct |
31 |
Correct |
14 ms |
10428 KB |
Output is correct |
32 |
Correct |
16 ms |
10452 KB |
Output is correct |
33 |
Correct |
14 ms |
10452 KB |
Output is correct |
34 |
Correct |
16 ms |
10428 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
59 ms |
12620 KB |
Output is correct |
37 |
Correct |
61 ms |
12732 KB |
Output is correct |
38 |
Correct |
93 ms |
13032 KB |
Output is correct |
39 |
Correct |
87 ms |
13076 KB |
Output is correct |
40 |
Correct |
89 ms |
13080 KB |
Output is correct |
41 |
Correct |
13 ms |
10452 KB |
Output is correct |
42 |
Correct |
90 ms |
12960 KB |
Output is correct |
43 |
Correct |
114 ms |
12948 KB |
Output is correct |
44 |
Correct |
88 ms |
12960 KB |
Output is correct |
45 |
Correct |
78 ms |
12968 KB |
Output is correct |
46 |
Correct |
83 ms |
12976 KB |
Output is correct |
47 |
Correct |
77 ms |
12972 KB |
Output is correct |