| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 689514 | Toxtaq | DNA 돌연변이 (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "grader.cpp"
using namespace std;
struct T{
int alph_A[3] = {0, 0, 0}, alph_B[3] = {0, 0, 0};
int diff = 0;
};
string a, b;
struct SegTree{
vector<T>sTree;
T comb(T a, T b){
T res;
res.diff = a.diff + b.diff;
res.alph_A[0] += a.alph_A[0];
res.alph_A[1] += a.alph_A[1];
res.alph_A[2] += a.alph_A[2];
res.alph_A[0] += b.alph_A[0];
res.alph_A[1] += b.alph_A[1];
res.alph_A[2] += b.alph_A[2];
res.alph_B[0] += a.alph_B[0];
res.alph_B[1] += a.alph_B[1];
res.alph_B[2] += a.alph_B[2];
res.alph_B[0] += b.alph_B[0];
res.alph_B[1] += b.alph_B[1];
res.alph_B[2] += b.alph_B[2];
return res;
}
void Build(int node, int l, int r){
if(l == r){
sTree[node].diff = (a[l] != b[l]);
if(a[l] == 'A')sTree[node].alph_A[0]++;
if(a[l] == 'T')sTree[node].alph_A[1]++;
if(a[l] == 'C')sTree[node].alph_A[2]++;
if(b[l] == 'A')sTree[node].alph_B[0]++;
if(b[l] == 'T')sTree[node].alph_B[1]++;
if(b[l] == 'C')sTree[node].alph_B[2]++;
}
else{
int mid = (l + r) >> 1;
Build(node * 2, l, mid);
Build(node * 2 + 1, mid + 1, r);
sTree[node] = comb(sTree[node * 2], sTree[node * 2 + 1]);
}
}
T Query(int node, int l, int r, int ql, int qr){
T Res;
if(ql <= l && r <= qr)return sTree[node];
if(ql > r || qr < l)return Res;
int mid = (l + r) >> 1;
T Lc = Query(node * 2, l, mid, ql, qr);
T Rc = Query(node * 2 + 1, mid + 1, r, ql, qr);
Res = comb(Lc, Rc);
return Res;
}
};
SegTree st;
void init(string A, string B){
a = " ", b = " ";
a += A, b += B;
st.sTree.resize(4 * A.length());
st.Build(1, 1, A.length());
}
int get_distance(int x, int y){
x++;
y++;
T q = st.Query(1, 1, a.length() - 1, x, y);
for(int i = 0;i < 3;++i){
if(q.alph_A[i] != q.alph_B[i])return -1;
}
return q.diff - 1;
}
//int main(){
// init("ATACAT", "ACTATA");
// cout << get_distance(3, 5);
//}