Submission #1234716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234716		hq77	Mutating DNA (IOI21_dna)	C++20	35 / 100	100 ms	15288 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#include <array>
using namespace std;

inline array<int,3> combine(const array<int,3>& a, const array<int,3>& b){
	return {a[0] + b[0], a[1] + b[1], a[2] + b[2]};
}
struct node{
    int s,e,m;
    node *l, *r;
    array<int,3> v;
    node(int ss,int ee):s(ss),e(ee),m((s+e)>>1),v{0,0,0}{
        if(s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
        }
    }
    void build(int x,int y,int pos, int neg){
        if(s==e){
            v[0]=y;
			v[1]=pos;
			v[2]=neg;
            return;
        }
        if(x<=m) l->build(x,y,pos,neg);
        else r->build(x,y,pos,neg);
        v=combine(l->v,r->v);
	}
	array<int,3> query(int x, int y){
        if(x<=s && y>=e)return v;
        if(y<=m) return l->query(x,y);
		if(x > m) return r->query(x, y);
        return combine(l->query(x,m),r->query(m+1,y));
	}

};
// node *st=new node(0,1e5);
node *st=nullptr;
void init(std::string a, std::string b) {
	int n=a.size();
	vector<int>v(n);
	if(st!=nullptr){
		delete st;
	}
	st=new node(0,n-1);
	for(int i=0;i<a.size();i++){
		if(a[i]=='A' && b[i]=='T')st->build(i, 1, 1, 0);
		else if(a[i]=='T' && b[i]=='A')st->build(i, -1, 0, 1);
		else st->build(i, 0, 0, 0);
	}
	
	// for(int i=0;i<a.size();i++){
	// 	if(v[i]==1)st->build(i,v[i],1,0);
	// 	else st->build(i,v[i],0,1);
	// }
}

int get_distance(int x, int y) {
	array<int, 3> result = st->query(x, y);
	if(result[0]!=0)return -1;
	else return result[1];
	return abs(result[0]);
}

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