Submission #1026703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026703		Gray	Mutating DNA (IOI21_dna)	C++17	56 / 100	368 ms	25940 KiB

dna

#include "dna.h"
#include <iostream>
#include <map>
#include <vector>

#define ll long long
#define ff first
#define ss second
#define ln "\n"

using namespace std;
map<char, ll> charmap = {{'A',0},{'C', 1},{'T', 2}};
struct segtree{
	struct node{
		vector<ll> a;
		ll icnt;
	};
	#define neutral {{0, 0, 0, 0}, 0}
	vector<node> t;
	ll sz, rsz;
	node merge(node l, node r){
		node nw; nw.icnt=l.icnt+r.icnt;
		nw.a.resize(4);
		for (ll i=0; i<4; i++){
			nw.a[i]=l.a[i]+r.a[i];
		}
		return nw;
	}
	void init(ll N){
		sz=N*4;
		rsz=N;
		t.resize(sz);
	}
	void build(ll tl, ll tr, ll v, string &a, string &b){
		if (tl==tr){
			t[v] = {{0, 0, 0, 0}, (a[tl]!=b[tl])};
			t[v].a[charmap[a[tl]]]++;
			t[v].a[charmap[b[tl]]]--;
		}else{
			ll tm = (tl+tr)/2;
			build(tl, tm, v*2, a, b);
			build(tm+1, tr, v*2+1, a, b);
			t[v]=merge(t[v*2], t[v*2+1]);
		}
	}
	node query(ll l, ll r, ll tl, ll tr, ll v){
		if (l==tl and r==tr){
			return t[v];
		}else if (l>r) return neutral;
		else{
			ll tm = (tl+tr)/2;
			return merge(query(l, min(r, tm), tl, tm, v*2), query(max(l, tm+1), r, tm+1, tr, v*2+1));
		}
	}
	void build(string &a, string &b){
		build(0, rsz-1, 1, a, b);
	}
	ll query(ll l, ll r){
		node ret = query(l, r, 0, rsz-1, 1);
		if (ret.a[0] or ret.a[1] or ret.a[2] or ret.a[3]) return -1;
		return query(l, r, 0, rsz-1, 1).icnt;
	}
};
segtree tr;
void init(std::string a, std::string b) {
	tr.init(a.length());
	tr.build(a, b);
}

int get_distance(int x, int y) {
	int ans = (int)tr.query(x, y);
	return ans/2+ans%2;
}

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