Submission #1262768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262768		tapilyoca	Mutating DNA (IOI21_dna)	C++20	56 / 100	229 ms	46660 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
template<typename T>
using vec = vector<T>;

using ll = long long;
using str = string;

struct Ans {
    ll A, T, C;
    
    Ans() : A(0), T(0), C(0) {}
    Ans(ll a, ll t, ll c) {
        A = a; T = t; C = c;
    }

    Ans operator+(const Ans &two) const {
        return Ans(A+two.A,T+two.T,C+two.C);
    }

    bool operator!=(const Ans&two) const {
        return not(A == two.A and T == two.T and C == two.C);
    }
};

struct Segtree {
    ll l, r;
    Segtree *lt, *rt;
    Ans freq;

    void combine() {
        freq = lt->freq + rt->freq;
    }

    Segtree() : l(0), r(0), lt(nullptr), rt(nullptr), freq(Ans(0,0,0)) {}

    Segtree(ll left, ll right, vec<Ans>&a) {
        l = left; r = right;
        lt = rt = nullptr;
        if(l == r) {
            freq = a[l];
            return;
        }
        ll m = (l+r)>>1;
        lt = new Segtree(l,m,a);
        rt = new Segtree(m+1,r,a);
        combine();
    }

    Ans query(ll ql, ll qr) {
        if(qr < l or r < ql) return {0,0,0};
        if(ql <= l and r <= qr) return freq;
        return lt->query(ql,qr) + rt->query(ql,qr);
    }
};

Segtree diffs, Atree, Btree;

void init(str a, str b) {
    ll n = a.length();
    vec<Ans> countA(n), countB(n);
    vec<Ans> mismatch(n);

    for(int i = 0; i < n; i++) {
        countA[i] = {0,0,0};
        countB[i] = {0,0,0};
        mismatch[i] = {0,0,0};

        mismatch[i].A = (a[i] != b[i]);
        if(a[i] == 'A') countA[i].A = 1;
        else if(a[i] == 'T') countA[i].T = 1;
        else if(a[i] == 'C') countA[i].C = 1;

        if(b[i] == 'A') countB[i].A = 1;
        else if(b[i] == 'T') countB[i].T = 1;
        else if(b[i] == 'C') countB[i].C = 1;
    }

    cerr << "Count done" << endl;

    diffs = Segtree(0,n-1,mismatch);
    Atree = Segtree(0,n-1,countA);
    Btree = Segtree(0,n-1,countB);

    cerr << "Segtrees done" << endl;
}

int get_distance(int x, int y) {
    
    Ans aCount = Atree.query(x,y);
    Ans bCount = Btree.query(x,y);
    if(aCount != bCount) {
        return -1;
    }

    ll ans = diffs.query(x,y).A;
    return (ans+1)/2;
}

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