제출 #561294

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
561294		AlperenT	DNA 돌연변이 (IOI21_dna)	C++17	100 / 100	92 ms	13528 KiB

dna

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

using namespace std;

const int N = 1e5 + 5;

int n;

string a, b;

struct Node{
	int ac, ca, at, ta, ct, tc;

	Node(){
		ac = ca = at = ta = ct = tc = 0;
	}

	void add(char x, char y){
		if(x == 'A' && y == 'C') ac++;
		if(x == 'C' && y == 'A') ca++;
		if(x == 'A' && y == 'T') at++;
		if(x == 'T' && y == 'A') ta++;
		if(x == 'C' && y == 'T') ct++;
		if(x == 'T' && y == 'C') tc++;
	}

	Node operator + (const Node &sc) const{
		Node c;

		c.ac = ac + sc.ac;
		c.ca = ca + sc.ca;
		c.at = at + sc.at;
		c.ta = ta + sc.ta;
		c.ct = ct + sc.ct;
		c.tc = tc + sc.tc;

		return c;
	}
};

struct SegTree{
	Node tree[N * 4];

	void build(int v = 1, int l = 0, int r = n - 1){
		if(l == r) tree[v].add(a[l], b[l]);
		else{
			int m = l + (r - l) / 2;

			build(v * 2, l, m);
			build(v * 2 + 1, m + 1, r);

			tree[v] = tree[v * 2] + tree[v * 2 + 1];
		}
	}

	Node query(int l, int r, int v = 1, int tl = 0, int tr = n - 1){
		if(l > r) return Node();
		else if(tl == l && tr == r) return tree[v];
		else{
			int tm = tl + (tr - tl) / 2;

			return query(l, min(tm, r), v * 2, tl, tm) + query(max(l, tm + 1), r, v * 2 + 1, tm + 1, tr);
		}
	}
};

SegTree sgt;

void init(string inp_a, string inp_b){
	a = inp_a, b = inp_b;

	n = a.size();

	sgt.build();
}

int get_distance(int x, int y){
	Node v = sgt.query(x, y);

	int ans = 0, tmp;

	tmp = min(v.ac, v.ca);

	ans += tmp;
	v.ac -= tmp;
	v.ca -= tmp;

	tmp = min(v.at, v.ta);

	ans += tmp;
	v.at -= tmp;
	v.ta -= tmp;

	tmp = min(v.ct, v.tc);

	ans += tmp;
	v.ct -= tmp;
	v.tc -= tmp;

	if(v.ac == v.ct && v.ct == v.ta) ans += v.ac * 2;
	else return -1;

	if(v.ca == v.at && v.at == v.tc) ans += v.ca * 2;
	else return -1;

	return ans;
}

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