제출 #470778

#제출 시각아이디문제언어결과실행 시간메모리
470778nicolaalexandraDNA 돌연변이 (IOI21_dna)C++17
56 / 100
108 ms13632 KiB
#include <bits/stdc++.h> #include "dna.h" #define DIM 100010 using namespace std; struct segment_tree{ int stare[7]; } aint[DIM*4],sol; string a,b; int sp_a0[DIM],sp_a1[DIM],sp_a2[DIM],sp_b0[DIM],sp_b1[DIM],sp_b2[DIM]; int n; void build (int nod, int st, int dr){ if (st == dr){ if (a[st-1] == 'A' && b[st-1] == 'C') aint[nod].stare[1] = 1; if (a[st-1] == 'A' && b[st-1] == 'T') aint[nod].stare[2] = 1; if (a[st-1] == 'C' && b[st-1] == 'A') aint[nod].stare[3] = 1; if (a[st-1] == 'C' && b[st-1] == 'T') aint[nod].stare[4] = 1; if (a[st-1] == 'T' && b[st-1] == 'A') aint[nod].stare[5] = 1; if (a[st-1] == 'T' && b[st-1] == 'C') aint[nod].stare[6] = 1; return; } int mid = (st+dr)>>1; build (nod<<1,st,mid); build ((nod<<1)|1,mid+1,dr); for (int i=1;i<=6;i++) aint[nod].stare[i] = aint[nod<<1].stare[i] + aint[(nod<<1)|1].stare[i]; } void query (int nod, int st, int dr, int x, int y){ if (x <= st && dr <= y){ for (int i=1;i<=6;i++) sol.stare[i] += aint[nod].stare[i]; return; } int mid = (st+dr)>>1; if (x <= mid) query (nod<<1,st,mid,x,y); if (y > mid) query ((nod<<1)|1,mid+1,dr,x,y); } void init (string A, string B){ n = A.size(); a = A, b = B; build (1,1,n); for (int i=1;i<=n;i++){ sp_a0[i] = sp_a0[i-1] + (a[i-1] == 'A'); sp_a1[i] = sp_a1[i-1] + (a[i-1] == 'C'); sp_a2[i] = sp_a2[i-1] + (a[i-1] == 'T'); sp_b0[i] = sp_b0[i-1] + (b[i-1] == 'A'); sp_b1[i] = sp_b1[i-1] + (b[i-1] == 'C'); sp_b2[i] = sp_b2[i-1] + (b[i-1] == 'T'); } } int get_distance (int x, int y){ x++, y++; int ans = 0; if (sp_a0[y] - sp_a0[x-1] != sp_b0[y] - sp_b0[x-1]) return -1; if (sp_a1[y] - sp_a1[x-1] != sp_b1[y] - sp_b1[x-1]) return -1; if (sp_a2[y] - sp_a2[x-1] != sp_b2[y] - sp_b2[x-1]) return -1; for (int i=1;i<=6;i++) sol.stare[i] = 0; query (1,1,n,x,y); int nr = min (sol.stare[1],min(sol.stare[4],sol.stare[5])); ans += 2 * nr; sol.stare[1] -= nr, sol.stare[4] -= nr, sol.stare[5] -= nr; nr = min (sol.stare[2],min(sol.stare[3],sol.stare[6])); ans += 2 * nr; sol.stare[2] -= nr, sol.stare[3] -= nr, sol.stare[6] -= nr; nr = min (sol.stare[1],sol.stare[3]); ans += nr; sol.stare[1] -= nr, sol.stare[3] -= nr; nr = min (sol.stare[2],sol.stare[5]); ans += nr; sol.stare[2] -= nr, sol.stare[5] -= nr; nr = min (sol.stare[4],sol.stare[6]); ans += nr; sol.stare[4] -= nr, sol.stare[6] -= nr; return ans; }
#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...