Submission #1234627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234627		gry3125	Mutating DNA (IOI21_dna)	C++20	0 / 100	26 ms	4928 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define ll long long int

using namespace std;
string a, b; int n;
vector<ll> as, bs;
// A = 0, T = 1

vector<int> t;
void init() {
	t.assign((1LL << 18)+5, 0LL);
}
void upd(int v, int tl, int tr, int pos, int val) {
	if (tl == tr) {t[v] = val; return;}
	int tm = (tl + tr) / 2;
	if (pos <= tm) upd(2*v, tl, tm, pos, val);
	else upd(2*v+1, tm+1, tr, pos, val);
	t[v] = t[2*v] + t[2*v+1];
}
ll query(int v, int tl, int tr, int l, int r) {
	if (l < r) return 0;
	if (l == tl && r == tr) return t[v];
	int tm = (tl + tr) / 2;
	ll lf = query(2*v, tl, tm, l, min(tm, r));
	ll rg = query(2*v+1, tm+1, tr, max(tm+1, l), r);
	return lf + rg;
}


void init(string aa, string bb) {
	a = aa; b = bb; n = a.size(); 
	as.resize(n); bs.resize(n); 
	if (a[0] == 'T') as[0]++;
	if (b[0] == 'T') bs[0]++;
	for (int i = 1; i < n; i++) {
		as[i] = as[i-1];
		bs[i] = bs[i-1];
		if (a[i] == 'T') as[i]++;
		if (b[i] == 'T') bs[i]++;
	}
	init();
	for (int i = 0; i < n; i++) {
		if (a[i] != b[i]) {
			upd(1, 1, (1LL << 18), i+1, 1);
		}
	}
}

int get_distance(int x, int y) {
	ll suma = as[y], sumb = bs[y];
	if (x > 0) {
		suma -= as[x-1]; sumb -= bs[x-1];
	}
	if (suma != sumb) return -1;

	if (x == y) {
		if (a[x] == b[x]) return 0;
		return -1;
	}
	if (x + 1 == y) {
		if (a[x] == b[x] && a[y] == b[y]) return 0;
		if (a[x] == b[y] && a[y] == b[x]) return 1;
		return -1;
	}
	
	ll ans = query(1, 1, (1LL << 18), x+1, y+1);
	return ans/2;
}

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