Submission #1053120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053120		MarwenElarbi	Mutating DNA (IOI21_dna)	C++17	100 / 100	73 ms	19540 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#include "dna.h"
const int nax=1e5+5;
struct DNA{
	int sumA,sumT,sumC,at,ac,ct,ca,ta,tc;
	DNA() : sumA(0),sumT(0),sumC(0),at(0),ac(0),ct(0),ca(0),ta(0),tc(0) {}
};
DNA segtree[nax*4];
string s,t;
DNA merge(DNA a,DNA b){
	DNA ans;
	ans.sumA=a.sumA+b.sumA;
	ans.sumT=a.sumT+b.sumT;
	ans.sumC=a.sumC+b.sumC;
	ans.ac=a.ac+b.ac;
	ans.tc=a.tc+b.tc;
	ans.ca=a.ca+b.ca;
	ans.ct=a.ct+b.ct;
	ans.ta=a.ta+b.ta;
	ans.at=a.at+b.at;
	return ans;
}
void build(int pos,int l,int r){
	if(l==r){
		if(s[l]=='A'){
			segtree[pos].sumA++;
			if(t[l]=='C') segtree[pos].ac++;
			if(t[l]=='T') segtree[pos].at++;
		}
		if(s[l]=='T'){
			segtree[pos].sumT++;
			if(t[l]=='C') segtree[pos].tc++;
			if(t[l]=='A') segtree[pos].ta++;
		}
		if(s[l]=='C'){
			segtree[pos].sumC++;
			if(t[l]=='A') segtree[pos].ca++;
			if(t[l]=='T') segtree[pos].ct++;
		}
		return;
	}
	int mid=(r+l)/2;
	build(pos*2+1,l,mid);
	build(pos*2+2,mid+1,r);
	segtree[pos]=merge(segtree[pos*2+1],segtree[pos*2+2]);
}
DNA nabba;
DNA query(int pos,int l,int r,int left,int right){
	if(l>r||l>right||r<left) return nabba;
	if(l>=left&&r<=right) return segtree[pos];
	int mid=(r+l)/2;
	return merge(query(pos*2+1,l,mid,left,right),query(pos*2+2,mid+1,r,left,right));
}
int pre[nax][3];
int n;
void init(std::string a, std::string b) {
	s=a;
	t=b;
	n=t.size();
	build(0,0,n-1);
	for (int i = 0; i < n; ++i)
	{
		pre[i+1][0]=pre[i][0]+(t[i]=='A');
		pre[i+1][1]=pre[i][1]+(t[i]=='T');
		pre[i+1][2]=pre[i][2]+(t[i]=='C');
	}
	return;
}

int get_distance(int x, int y){
	int a=pre[y+1][0]-pre[x][0];
	int t=pre[y+1][1]-pre[x][1];
	int c=pre[y+1][2]-pre[x][2];
	DNA ans=query(0,0,n-1,x,y);
	if(ans.sumA!=a||ans.sumT!=t||ans.sumC!=c) return -1;
	return max(ans.ta,ans.at)+max(ans.ca,ans.ac)+min(ans.ct,ans.tc);

}

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