Submission #689520

#	Time	Username	Problem	Language	Result	Execution time	Memory
689520		Toxtaq	Mutating DNA (IOI21_dna)	C++17	0 / 100	79 ms	13584 KiB

dna

#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);
//}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 22
• Subtask 3: 0 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16