Submission #739884

#	Time	Username	Problem	Language	Result	Execution time	Memory
739884		abczz	Mutating DNA (IOI21_dna)	C++17	100 / 100	107 ms	16432 KiB

dna

#include <iostream>
#include <array>
#include "dna.h"
#define ll long long

using namespace std;

array<ll, 6> st[400000], Q;
string S, T, D[6] = {"AT", "AC", "TC", "CT", "CA", "TA"};
ll n, f, z, C[26], R[6], mx;

void build(ll id, ll l, ll r) {
	if (l == r) {
		for (int i=0; i<6; ++i) {
			if (D[i][0] == S[l] && D[i][1] == T[l]) {
				++st[id][i];
				break;
			}
		}
		return;
	}
	ll mid = (l+r)/2, z;
	build(id*2, l, mid);
	build(id*2+1, mid+1, r);
	st[id] = st[id*2];
	for (int i=0; i<6; ++i) {
		st[id][i] += st[id*2+1][i];
	}
}

void query(ll id, ll l, ll r, ll ql, ll qr) {
	if (r < ql || qr < l) return;
	else if (ql <= l && r <= qr) {
		for (int i=0; i<6; ++i) {
			Q[i] += st[id][i];
		}
		return;
	}
	ll mid = (l+r)/2;
	query(id*2, l, mid, ql, qr);
	query(id*2+1, mid+1, r, ql, qr);
}

void init(std::string a, std::string b) {
	S = a, T = b;
	n = a.size();
	C['A'-'A'] = 0, C['T'-'A'] = 1, C['C'-'A'] = 2;
	build(1, 0, n-1);
}

int get_distance(int x, int y) {
	for (int i=0; i<6; ++i) R[i] = Q[i] = 0;
	f = mx = 0;
	query(1, 0, n-1, x, y);
	for (int i=0; i<3; ++i) {
		z = min(Q[i], Q[5-i]);
		Q[i] -= z, Q[5-i] -= z;
		f += z;
	}
	for (int i=0; i<6; ++i) {
		mx = max(mx, Q[i]);
		for (int j=0; j<2; ++j) {
			R[C[D[i][j]-'A']+j*3] += Q[i];
		}
	}
	for (int i=0; i<3; ++i) {
		if (R[i] != R[i+3]) return -1;
	}
	return f+mx*2;
}

Compilation message (stderr)

dna.cpp: In function 'void build(long long int, long long int, long long int)':
dna.cpp:22:20: warning: unused variable 'z' [-Wunused-variable]
   22 |  ll mid = (l+r)/2, z;
      |                    ^

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