#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
struct node{
int numAT,numAC,numTC,cnt;
};
node f(node x,node y){
node z;
z=x;
z.numAT+=y.numAT;
z.numAC+=y.numAC;
z.numTC+=y.numTC;
z.cnt+=y.cnt;
int num1,num2,num3;
if(x.numAT>=0){
num1=max(z.numAT,0);
}
else{
num1=min(z.numAT,0);
}
if(x.numAC>=0){
num2=max(z.numAC,0);
}
else{
num2=min(z.numAC,0);
}
if(x.numTC>=0){
num3=max(z.numTC,0);
}
else{
num3=min(z.numTC,0);
}
if(abs(x.numAT)>abs(num1)){
z.cnt+=abs(num1-x.numAT);
}
if(abs(x.numAC)>abs(num2)){
z.cnt+=abs(num2-x.numAC);
}
if(abs(x.numTC)>abs(num3)){
z.cnt+=abs(num3-x.numTC);
}
return z;
}
struct segtree{
int size;
vector<node> tree;
void init(int n){
size=1;
while(size<n){
size*=2;
}
node nd;
nd.numAC=0;
nd.numAT=0;
nd.numTC=0;
nd.cnt=0;
tree.assign(2*size,nd);
}
void build(string &a,string &b,int x,int lx,int rx){
if(rx-lx==1){
if(a[lx]!=b[lx]){
if(a[lx]=='A' && b[lx]=='T'){
tree[x].numAT=1;
}
else if(a[lx]=='T' && b[lx]=='A'){
tree[x].numAT=-1;
}
else if(a[lx]=='A' && b[lx]=='C'){
tree[x].numAC=1;
}
else if(a[lx]=='C' && b[lx]=='A'){
tree[x].numAC=-1;
}
else if(a[lx]=='T' && b[lx]=='C'){
tree[x].numTC=1;
}
else{
tree[x].numTC=-1;
}
}
return;
}
int m=(lx+rx)/2;
build(a,b,2*x+1,lx,m);
build(a,b,2*x+2,m,rx);
tree[x]=f(tree[2*x+1],tree[2*x+2]);
}
void build(string &a,string &b){
build(a,b,0,0,size);
}
node get_res(int l,int r,int x,int lx,int rx){
if(lx>=r || rx<=l){
node nd;
nd.numAC=0;
nd.numAT=0;
nd.numTC=0;
nd.cnt=0;
return nd;
}
if(lx>=l && rx<=r){
return tree[x];
}
node s1,s2;
int m=(lx+rx)/2;
s1=get_res(l,r,2*x+1,lx,m);
s2=get_res(l,r,2*x+2,m,rx);
return f(s1,s2);
}
node get_res(int l,int r){
return get_res(l,r+1,0,0,size);
}
};
segtree st;
void init(std::string a, std::string b) {
int n=a.size();
st.init(n);
st.build(a,b);
}
int get_distance(int x, int y) {
node nd=st.get_res(x,y);
int num1,num2,num3;
num1=num2=num3=0;
num1+=nd.numAC;
num2-=nd.numAC;
num1+=nd.numAT;
num3-=nd.numAT;
num3+=nd.numTC;
num2-=nd.numTC;
if(num1!=0 || num2!=0 || num3!=0){
return -1;
}
else{
return nd.cnt+abs(nd.numAC)*2;
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
56 ms |
6220 KB |
Output is correct |
2 |
Correct |
76 ms |
7608 KB |
Output is correct |
3 |
Correct |
56 ms |
7492 KB |
Output is correct |
4 |
Correct |
60 ms |
7572 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 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 |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
304 KB |
Output is correct |
4 |
Correct |
7 ms |
5164 KB |
Output is correct |
5 |
Correct |
7 ms |
5204 KB |
Output is correct |
6 |
Correct |
7 ms |
5080 KB |
Output is correct |
7 |
Correct |
7 ms |
5052 KB |
Output is correct |
8 |
Correct |
7 ms |
5204 KB |
Output is correct |
9 |
Correct |
6 ms |
5204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
304 KB |
Output is correct |
4 |
Correct |
7 ms |
5164 KB |
Output is correct |
5 |
Correct |
7 ms |
5204 KB |
Output is correct |
6 |
Correct |
7 ms |
5080 KB |
Output is correct |
7 |
Correct |
7 ms |
5052 KB |
Output is correct |
8 |
Correct |
7 ms |
5204 KB |
Output is correct |
9 |
Correct |
6 ms |
5204 KB |
Output is correct |
10 |
Correct |
56 ms |
7560 KB |
Output is correct |
11 |
Correct |
63 ms |
7568 KB |
Output is correct |
12 |
Correct |
85 ms |
7888 KB |
Output is correct |
13 |
Correct |
85 ms |
7924 KB |
Output is correct |
14 |
Correct |
92 ms |
7948 KB |
Output is correct |
15 |
Correct |
95 ms |
7952 KB |
Output is correct |
16 |
Correct |
78 ms |
7824 KB |
Output is correct |
17 |
Correct |
83 ms |
7804 KB |
Output is correct |
18 |
Correct |
79 ms |
7816 KB |
Output is correct |
19 |
Correct |
75 ms |
7764 KB |
Output is correct |
20 |
Correct |
76 ms |
7844 KB |
Output is correct |
21 |
Correct |
75 ms |
7852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
304 KB |
Output is correct |
4 |
Correct |
7 ms |
5164 KB |
Output is correct |
5 |
Correct |
7 ms |
5204 KB |
Output is correct |
6 |
Correct |
7 ms |
5080 KB |
Output is correct |
7 |
Correct |
7 ms |
5052 KB |
Output is correct |
8 |
Correct |
7 ms |
5204 KB |
Output is correct |
9 |
Correct |
6 ms |
5204 KB |
Output is correct |
10 |
Correct |
8 ms |
5076 KB |
Output is correct |
11 |
Correct |
7 ms |
5332 KB |
Output is correct |
12 |
Correct |
8 ms |
5076 KB |
Output is correct |
13 |
Correct |
8 ms |
5168 KB |
Output is correct |
14 |
Correct |
8 ms |
5204 KB |
Output is correct |
15 |
Correct |
7 ms |
5204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
56 ms |
6220 KB |
Output is correct |
2 |
Correct |
76 ms |
7608 KB |
Output is correct |
3 |
Correct |
56 ms |
7492 KB |
Output is correct |
4 |
Correct |
60 ms |
7572 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 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 |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
304 KB |
Output is correct |
11 |
Correct |
7 ms |
5164 KB |
Output is correct |
12 |
Correct |
7 ms |
5204 KB |
Output is correct |
13 |
Correct |
7 ms |
5080 KB |
Output is correct |
14 |
Correct |
7 ms |
5052 KB |
Output is correct |
15 |
Correct |
7 ms |
5204 KB |
Output is correct |
16 |
Correct |
6 ms |
5204 KB |
Output is correct |
17 |
Correct |
56 ms |
7560 KB |
Output is correct |
18 |
Correct |
63 ms |
7568 KB |
Output is correct |
19 |
Correct |
85 ms |
7888 KB |
Output is correct |
20 |
Correct |
85 ms |
7924 KB |
Output is correct |
21 |
Correct |
92 ms |
7948 KB |
Output is correct |
22 |
Correct |
95 ms |
7952 KB |
Output is correct |
23 |
Correct |
78 ms |
7824 KB |
Output is correct |
24 |
Correct |
83 ms |
7804 KB |
Output is correct |
25 |
Correct |
79 ms |
7816 KB |
Output is correct |
26 |
Correct |
75 ms |
7764 KB |
Output is correct |
27 |
Correct |
76 ms |
7844 KB |
Output is correct |
28 |
Correct |
75 ms |
7852 KB |
Output is correct |
29 |
Correct |
8 ms |
5076 KB |
Output is correct |
30 |
Correct |
7 ms |
5332 KB |
Output is correct |
31 |
Correct |
8 ms |
5076 KB |
Output is correct |
32 |
Correct |
8 ms |
5168 KB |
Output is correct |
33 |
Correct |
8 ms |
5204 KB |
Output is correct |
34 |
Correct |
7 ms |
5204 KB |
Output is correct |
35 |
Correct |
0 ms |
212 KB |
Output is correct |
36 |
Correct |
56 ms |
7568 KB |
Output is correct |
37 |
Correct |
62 ms |
7576 KB |
Output is correct |
38 |
Correct |
94 ms |
7908 KB |
Output is correct |
39 |
Correct |
96 ms |
7980 KB |
Output is correct |
40 |
Correct |
98 ms |
7960 KB |
Output is correct |
41 |
Correct |
6 ms |
5148 KB |
Output is correct |
42 |
Correct |
95 ms |
7772 KB |
Output is correct |
43 |
Correct |
93 ms |
7860 KB |
Output is correct |
44 |
Correct |
94 ms |
7904 KB |
Output is correct |
45 |
Correct |
67 ms |
7832 KB |
Output is correct |
46 |
Correct |
77 ms |
7840 KB |
Output is correct |
47 |
Correct |
70 ms |
7848 KB |
Output is correct |