제출 #1289293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289293		Ekber_Ekber	DNA 돌연변이 (IOI21_dna)	C++20	0 / 100	125 ms	30392 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;

struct wavelet{
	int mn, mx, nxt=1;
	vector <vector <int>> t, pr;
	vector <int> L, R;
	void init(int mi, int ma) {
		mn = mi, mx = ma;
		t.pb({});
		pr.pb({});
		L.pb(-1);
		R.pb(-1);
	}
	void build(int v, int tl, int tr, vector <int> &a) {
		int tm = (tl + tr) / 2;
		if (v == 1) {
			t.pb({});
			for (int i = 0; i < a.size(); i++) t[v].pb(a[i]);
		}
		while (pr.size() <= v) pr.pb({});
		pr[v].pb(0);
		for (int i = 0; i < t[v].size(); i++) {
			if (t[v][i] <= tm) pr[v].pb(1);
			else pr[v].pb(0);
		}
		for (int i = 1; i < pr[v].size(); i++) pr[v][i] += pr[v][i-1];
		if (tl == tr) return;
		while (L.size() <= v) L.pb(-1);
		while (R.size() <= v) R.pb(-1);
		L[v] = ++nxt;
		R[v] = ++nxt;
		while (t.size() <= R[v]) t.pb({});
		for (int i = 0; i < t[v].size(); i++) {
			if (t[v][i] <= tm) t[L[v]].pb(t[v][i]);
			else t[R[v]].pb(t[v][i]);
		}
		if (t[L[v]].size()) build(L[v], tl, tm, a);
		if (t[R[v]].size()) build(R[v], tm+1, tr, a);
	}
	void bld(vector <int> &v) { build(1, mn, mx, v); }
	int findk(int v, int tl, int tr, int l, int r, int k) {
		if (tl == tr) return tl;
		int tm = (tl + tr) / 2;
		int ct = pr[v][r+1] - pr[v][l];
		if (ct >= k) return findk(L[v], tl, tm, pr[v][l], pr[v][r+1] - 1, k);
		else return findk(R[v], tm+1, tr, l - pr[v][l], r - pr[v][r+1], k - ct);
	}
	int kth(int l, int r, int k) { return findk(1, mn, mx, l, r, k); }
	int findsmallerk(int v, int tl, int tr, int l, int r, int k) {
		if (l > r) return 0;
		if (tl == tr) return r - l + 1;
		int tm = (tl + tr) / 2;
		if (k <= tm) {
			return findsmallerk(L[v], tl, tm, pr[v][l], pr[v][r+1] - 1, k);
		}
		else {
			return findsmallerk(R[v], tm+1, tr, l - pr[v][l], r - pr[v][r+1], k) + pr[v][r+1] - pr[v][l];
		}
	}
	int smallk(int l, int r, int k) { return findsmallerk(1, mn, mx, l, r, k); }
	int findbiggerk(int v, int tl, int tr, int l, int r, int k) {
		if (l > r) return 0;
		if (tl == tr) return r - l + 1;
		int tm = (tl + tr) / 2;
		if (k <= tm) {
			return findbiggerk(L[v], tl, tm, pr[v][l], pr[v][r+1] - 1, k) + r - l + 1 - pr[v][r+1] + pr[v][l];
		}
		else {
			return findbiggerk(R[v], tm+1, tr, l - pr[v][l], r - pr[v][r+1], k);
		}
	}
	int bigk(int l, int r, int k) { return findbiggerk(1, mn, mx, l, r, k); }
};

vector <int> pr1[3], pr2[3], is;
wavelet t;
vector <int> l;

void init(string a, string b) {
	int n = a.size();
	for (int i = 0; i < 3; i++) {
		pr1[i].assign(n, 0);
		pr2[i].assign(n, 0);
	}
	is.assign(n, 0);
	for (int i = 0; i < n; i++) {
		if (a[i] == 'A') pr1[0][i]++;
		else if (a[i] == 'T') pr1[1][i]++;
		else pr1[2][i]++;
		if (b[i] == 'A') pr2[0][i]++;
		else if (b[i] == 'T') pr2[1][i]++;
		else pr2[2][i]++;
	}
	for (int i = 0; i < n; i++) {
		if (a[i] != b[i]) is[i]++;
	}
	map <pair<char, char>, vector <int>> m;
	vector <pair<int, int>> rn;
	for (int i = 0; i < n; i++) {
		if (m[{b[i], a[i]}].size()) {
			rn.pb({m[{b[i], a[i]}].back(), i});
			m[{b[i], a[i]}].pop_back();
		}
		else m[{a[i], b[i]}].pb(i);
	}
	sort(all(rn));
	vector <int> r;
	for (auto &i : rn) {
		l.pb(i.ff);
		r.pb(i.ss);
	}
	t.init(0, n);
	t.bld(r);
}

int get_distance(int x, int y) {
	for (int i = 0; i < 3; i++) {
		int a = pr1[i][y] - (x == 0 ? 0 : pr1[i][x-1]);
		int b = pr2[i][y] - (x == 0 ? 0 : pr2[i][x-1]);
		if (a != b) return -1;
	}
	int res = is[y] - (x == 0 ? 0 : is[x-1]);
	int id = lower_bound(all(l), x) - l.begin();
	return res - t.smallk(id, l.size()-1, y);
}

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