Submission #599261

#	Time	Username	Problem	Language	Result	Execution time	Memory
599261		lcj	Mutating DNA (IOI21_dna)	C++17	35 / 100	56 ms	5324 KiB

dna

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define LSOne(S) ((S) & -(S))

struct Fenwick {
    vector<int> ft;
    Fenwick(int n) : ft(n+1, 0) {}
    int qry(int i) {
        int su = 0;
        for (; i > 0; i -= LSOne(i)) {
            su += ft[i];
        }
        return su;
    }
    int qry(int i, int j) {
        return qry(j)-qry(i-1);
    }
    void upd(int i, int dv) {
        for (; i < (int)ft.size(); i += LSOne(i)) {
            ft[i] += dv;
        }
    }
};

map<char, int> cmap = {
    {'A', 0},
    {'T', 1},
    {'C', 2}
};
vector<Fenwick> o1;
vector<Fenwick> o2;

void init(string a, string b) {
    int n = a.size();
    o1.assign(3, Fenwick(n));
    o2.assign(3, Fenwick(n));
    for (int i = 0; i < n; i++)
    {
        if (a[i] == b[i]) continue;
        o1[cmap[a[i]]].upd(i+1, 1);
        o2[cmap[b[i]]].upd(i+1, 1);
    }
}

int get_distance(int x, int y) {
    int su = 0;
    bool val = 1;
    for (int i = 0; i < 3; i++)
    {
        if (o1[i].qry(x+1, y+1) != o2[i].qry(x+1, y+1)) {
            val = 0;
            break;
        }
        su += o1[i].qry(x+1, y+1);
    }
    if (!val) {
        return -1;
    }
    if (su == 0) return 0;
    return su/2;
}

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