Submission #1184170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184170		hyakup	Mutating DNA (IOI21_dna)	C++20	100 / 100	1117 ms	403416 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 4e5 + 10;

struct Node{
	vector<int> cont;
	vector<vector<int>> pares;
	Node( int a = 3, int b = 3 ){
		cont.resize(3);
		pares.resize(3, vector<int>(3));
		if( a < 3 && b < 3 ){
			cont[a]++; cont[b]--;
			pares[a][b]++;
		}
	}

	Node operator + ( Node n ){
		Node resp;
		for( int i = 0; i < 3; i++ ){
			resp.cont[i] = cont[i] + n.cont[i];
			for( int j = 0; j < 3; j++ ) resp.pares[i][j] = pares[i][j] + n.pares[i][j];
		}
		return resp;
	}
} seg[4*maxn];

int id( char c ){
	if( c == 'A' ) return 0;
	if( c == 'T' ) return 1;
	return 2;
}

void build( int pos, int ini, int fim, string &a, string &b ){
	if( ini == fim ){ seg[pos] = Node( id(a[ini]), id(b[ini]) ); return; }
	int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
	build( l, ini, mid, a, b ); build( r, mid + 1, fim, a, b );
	seg[pos] = seg[l] + seg[r];
}

Node query( int pos, int ini, int fim, int ki, int kf ){
	if( ki > fim || ini > kf ) return seg[0];
	if( ki <= ini && fim <= kf ) return seg[pos];
	int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
	return query( l, ini, mid, ki, kf ) + query( r, mid + 1, fim, ki, kf );
}

int n;

void init( string a, string b ){
	n = a.size();
	build( 1, 0, n - 1, a, b );
}

int get_distance(int l, int r) {
	Node resp = query( 1, 0, n - 1, l, r );
	bool ok = true;
	for( int i = 0; i < 3; i++ ) if( resp.cont[i] != 0 ) ok = false;
	if( !ok ) return -1;

	int tot = 0;

	for( int i = 0; i < 3; i++ ){
		resp.pares[i][i] = 0;
		for( int j = i + 1; j < 3; j++ ){
			int aux = min( resp.pares[i][j], resp.pares[j][i] );
			resp.pares[i][j] -= aux; resp.pares[j][i] -= aux;
			tot += aux;
		}
	}

	int qtd = 0;
	for( int i = 0; i < 3; i++ ) for( int j = 0; j < 3; j++ ) qtd = max( qtd, resp.pares[i][j] );

	tot += 2*qtd;

	return tot;
}

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