Submission #588999

#	Time	Username	Problem	Language	Result	Execution time	Memory
588999		l_reho	Mutating DNA (IOI21_dna)	C++17	22 / 100	1593 ms	7220 KiB

dna

#include "dna.h"

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

int N;
vector<int> MN;
vector<int> MX;

vector<int> V;
vector<bool> visited;

void build(int p, int L, int R){
	
	if(L == R){
		MN[p] = L;
		MX[p] = L;
				
		return;
	}
	
	int mid = (L+R)/2;
	
	build(p*2, L, mid);
	build(p*2+1, mid+1, R);
		
	int idx1 = MN[p*2];
	int idx2 = MN[p*2+1];
	
	if(V[idx1] <= V[idx2]) MN[p] = idx1;
	else MN[p] = idx2;
	
	idx1 = MX[p*2];
	idx2 = MX[p*2+1];
	
	if(V[idx1] >= V[idx2]) MX[p] = idx1;
	else MX[p] = idx2;
	
	
	
}

int get(int p, int L, int R, int i, int j, int v){
	
	if(i > R || j < L) return -1;
	
	if(i <= L && R <= j){
		if((v == -1 && V[MN[p]] != -1) || (v == 1 && V[MX[p]] != 1)) return -1;
		int low = L;
		int high = R;
		// int ret = -1;
		
		while(low < high){
			int mid = low +(high-low)/2;
			
			if((v == -1 && V[MN[p*2]] == -1) || (v == 1 && V[MX[p*2]] == 1) ){
				// ret = mid;
				high = mid;
				p*=2;
			}else low = mid+1, p = 2*p+1;
		}
		
		return low;
		
	}
	
	int mid = (L+R)/2;
	
	int ret1 = get(p*2, L, mid, i, j, v);
	if(ret1 != -1) return ret1;
	
	return get(p*2+1, mid+1, R, i, j, v);
	
	
}

void update(int p, int L, int R, int i, int v){
	
	if(i > R || i < L) return;
	
	if(i == R && L == i){
		MX[p] = L;
		MN[p] = L;
		
		V[i] = v;
		return;
	}
	
	int mid = (L+R)/2;
	
	update(p*2, L, mid, i, v);
	update(p*2+1, mid+1, R, i, v);
	
			
	int idx1 = MN[p*2];
	int idx2 = MN[p*2+1];
	
	if(V[idx1] <= V[idx2]) MN[p] = idx1;
	else MN[p] = idx2;
	
	idx1 = MX[p*2];
	idx2 = MX[p*2+1];
	
	if(V[idx1] >= V[idx2]) MX[p] = idx1;
	else MX[p] = idx2;
	
}

void init(std::string a, std::string b) {
	N = a.length();
	
	V.assign(N, 0);
	visited.assign(N, false);
	
	MN.assign(N*4+1, 0);
	MX.assign(N*4+1, 0);
	
	for(int i = 0; i < N; i++){
		if(a[i] == 'T' && b[i] == 'A') V[i] = 1;
		if(a[i] == 'A' && b[i] == 'T') V[i] = -1;
		if(a[i] == b[i]) V[i] = 0;
	}
	// ATTATATA TATTATTA
	
	build(1, 0, N-1);
	
}

int get_distance(int x, int y) {
	vector<int> init = V;
	
	int cnt = 0;
	bool ok = true;
	
	for(int i = x; i <= y; i++){
		int idx = -1;
		
		if(i == y && V[i] != 0){
			ok = false;
			break;
		}
		if(V[i] == 1)
			idx = get(1, 0, N-1, i+1, y, -1);			
		else if(V[i] == -1)
			idx = get(1, 0, N-1, i+1, y, 1);
		else continue;
		
		
		if(idx == -1) {
			ok = false;
			break;
		}
		
		cnt++;
		
		update(1, 0, N-1, idx, 0);
		
	}
	
	for(int i = x; i <= y; i++){
		update(1, 0, N-1, i, init[i]);
	}
	if(!ok) return -1;
	
	return cnt;
}

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