Submission #826006

#	Time	Username	Problem	Language	Result	Execution time	Memory
826006		TahirAliyev	Mutating DNA (IOI21_dna)	C++17	100 / 100	104 ms	14088 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e5 + 5;

array<array<int, 3>, 3> tree[4 * MAX];

vector<int> v1, v2;
int n;

array<array<int, 3>, 3> combine(array<array<int, 3>, 3> a, array<array<int, 3>, 3> b){
    array<array<int, 3>, 3> c;
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            c[i][j] = a[i][j] + b[i][j];
        }
    }
    return c;
}

void build(int node, int l, int r){
    if(l == r) {
        tree[node][v1[l]][v2[l]]++;
        return;
    }
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    tree[node] = combine(tree[2 * node], tree[2 * node + 1]);
}

array<array<int, 3>, 3> ask(int node, int l, int r, int ql, int qr){
    if(r < ql || qr < l){
        return array<array<int, 3>, 3>();
    }
    if(ql <= l && r <= qr){
        return tree[node];
    }
    int mid = (l + r) / 2;
    return combine(ask(2 * node, l, mid, ql, qr), ask(2 * node + 1, mid + 1, r, ql, qr));
}

map<char, int> mp = {{'A', 0}, {'T', 1}, {'C', 2}};

void init(string a, string b) {
    n = a.size();
    for (int i = 0; i < n; i++)
    {
        v1.push_back(mp[a[i]]);
    }
    for (int i = 0; i < n; i++)
    {
        v2.push_back(mp[b[i]]);
    }
    build(1, 0, n - 1);
}

int get_distance(int x, int y) {
    array<array<int, 3>, 3> a = ask(1, 0, n - 1, x, y);
    int letters[3];
    memset(letters, 0, sizeof(letters));
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            letters[i] += a[i][j];
            letters[j] -= a[i][j];
        }
    }
    for (int i = 0; i < 3; i++)
    {
        if(letters[i] != 0) {
            return -1;
        }
    }
    
    int p = min(a[0][1], a[1][0]) + min(a[1][2], a[2][1]) + min(a[0][2], a[2][0]);
    int s = a[0][0] + a[1][1] + a[2][2];
    int t = (y - x + 1) - p * 2 - s;
    return p + (t / 3 * 2);
}

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