제출 #689520

#제출 시각아이디문제언어결과실행 시간메모리
689520ToxtaqDNA 돌연변이 (IOI21_dna)C++17
0 / 100
79 ms13584 KiB
#include<bits/stdc++.h> #include "dna.h" 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; for(int i = 0;i < 3;++i){ res.alph_A[i] += a.alph_A[i]; res.alph_A[i] += b.alph_A[i]; res.alph_B[i] += a.alph_B[i]; res.alph_B[i] += b.alph_B[i]; } 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); //}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...