Submission #690989

#	Time	Username	Problem	Language	Result	Execution time	Memory
690989		Huseyn123	Mutating DNA (IOI21_dna)	C++17	100 / 100	98 ms	7980 KiB

dna

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

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