제출 #996685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
996685		overwatch9	DNA 돌연변이 (IOI21_dna)	C++17	0 / 100	173 ms	2644 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string A, B;
struct node {
	ll val = 0, lz = 0;
	bool pd = false;
};
struct stree {
	#define lc v*2
	#define rc v*2+1
	vector <node> tree;
	stree (int s) {
		tree.resize(s * 4);
	}
	void pushup(int v) {
		tree[v].val = tree[lc].val + tree[rc].val;
	}
	void pushdown(int v) {
		if (!tree[v].pd)
			return;
		tree[v].pd = false;
		tree[lc].pd = tree[rc].pd = true;
		tree[lc].val += tree[v].lz;
		tree[rc].val += tree[v].lz;
		tree[lc].lz += tree[v].lz;
		tree[rc].lz += tree[v].lz;
		tree[v].lz = 0;
	}
	void update (int v, int tl, int tr, int l, int r, int val) {
		if (tl > r || tr < l)
			return;
		if (tl >= l && tr <= r) {
			tree[v].lz += val;
			tree[v].val += val;
			tree[v].pd = true;
			return;
		}
		pushdown(v);
		int tm = (tl + tr) / 2;
		update(lc, tl, tm, l, r, val);
		update(rc, tm+1, tr, l, r, val);
		pushup(v);
	}
	ll query(int v, int tl, int tr, int l, int r) {
		if (tl > r || tr < l)
			return 0;
		if (tl >= l && tr <= r)
			return tree[v].val;
		pushdown(v);
		int tm = (tl + tr) / 2;
		ll a = query(lc, tl, tm, l, r);
		ll b = query(rc, tm+1, tr, l, r);
		return a + b;
	}
};
void init(std::string a, std::string b) {
	A = a;
	B = b;
}

int get_distance(int x, int y) {
	string a = A.substr(x, y - x + 1);
	string b = B.substr(x, y - x + 1);
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	if (a != b)
		return -1;
	a = A.substr(x, y - x + 1);
	b = B.substr(x, y - x + 1);
	vector <queue <int>> pos(26);
	for (int i = 0; i < y - x + 1; i++)
		pos[b[i] - 'A'].push(i);
	int sz = y - x + 1;
	stree tree(sz + 1);
	ll ans = 0;

	for (int i = 0; i < y - x + 1; i++) {
		int j = pos[a[i] - 'A'].front();
		pos[a[i] - 'A'].pop();
		ll res = 0;
		if (i < j)
			res = tree.query(1, 0, sz, i+1, j);
		else
			res = tree.query(1, 0, sz, j, i-1);
		ans += max(0LL, abs(i - j) - res);
		if (i < j)
			tree.update(1, 0, sz, i+1, j, 1);
		else
			tree.update(1, 0, sz, j, i-1, 1);
	}
	return ans;
}

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