Submission #1234860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234860		hq77	Mutating DNA (IOI21_dna)	C++20	In queue	0 ms	0 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){
        if(s==e){
            v[0]=y;
			v[1]=pos;
			// v[2]=A; v[3]=C; v[4]=T;
            return;
        }
        if(x<=m) l->build(x,y,pos);
        else r->build(x,y,pos);
        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));
	}

};
vector<vector<int>>v;
// node *st=new node(0,1e5);
node *st=nullptr;
string aa,bb;
void init(std::string a, std::string b) {
	aa=a;bb=b;
	int n=a.size();
	v.resize(6,vector<int>(n+1,0));
	for(int i=1;i<=n;i++){
		// if(i>1){
			v[0][i]=v[0][i-1];v[1][i]=v[1][i-1];
			v[2][i]=v[2][i-1];v[3][i]=v[3][i-1];
			v[4][i]=v[4][i-1];v[5][i]=v[5][i-1];
		// }
		if(a[i-1]=='A')v[0][i]++; if(b[i-1]=='A')v[3][i]++; 
		if(a[i-1]=='C')v[1][i]++; if(b[i-1]=='C')v[4][i]++; 
		if(a[i-1]=='T')v[2][i]++; if(b[i-1]=='T')v[5][i]++; 
	}
	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') || (a[i]=='T' && b[i]=='C'))st->build(i, 1, 1);
		else if((a[i]=='T' && b[i]=='A') || (a[i]=='C' && b[i]=='T'))st->build(i, -1, 0);
		else if(a[i]=='A' && b[i]=='C')st->build(i, 2, 1);
		else if(a[i]=='C' && b[i]=='A')st->build(i,-2,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) {
	if(y==x){if(aa[x]==bb[x])return 0; else return -1;}

	if(y-1==x){
		if(aa[x]==bb[x] && aa[y]==bb[y])return 0;
		else if(aa[x]==bb[y] && bb[x]==aa[y])return 1;
		else return -1;
	}
	if(y-2==x){
		if(aa[x]==bb[x] && aa[x+1]==bb[x+1] && aa[y]==bb[y])return 0;
		else if(aa[x]==bb[x] && aa[x+1]==bb[y] && aa[y]==bb[x+1])return 1;
		else if(aa[x]==bb[x+1] && aa[x+1]==bb[x] && aa[y]==bb[y])return 1;
		else if(aa[y]==bb[x] && aa[x+1]==bb[x+1] && aa[x]==bb[y])return 1;
		else if(aa[x]==bb[y] && aa[x+1]==bb[x] && aa[x+2]==bb[x+1])return 2;
		else if(aa[x]==bb[x+1] && aa[x+1]==bb[y] && aa[y]==bb[x]) return 2;
		else return -1;
	}
	array<int, 3> result = st->query(x, y);
	// for(int i:result)cout<<i<<" ";
	// cout<<v[0][y+1]-v[0][x]<<" "<<v[3][y+1]-v[3][x]<<" "<<v[1][y+1]-v[1][x]<<" "<<v[4][y+1]-v[4][x]<<" "<<v[2][y+1]-v[2][x]<<" "<<v[5][y+1]-v[5][x]<<" ";
	if(v[0][y+1]-v[0][x] != v[3][y+1]-v[3][x]) return -1;
	if(v[1][y+1]-v[1][x] != v[4][y+1]-v[4][x]) return -1;
	if(v[2][y+1]-v[2][x] != v[5][y+1]-v[5][x]) return -1;
	if(result[0]!=0)return -1;
	else return result[1];
}

int main(){
	int n,q;cin>>n>>q;
	string a,b;cin>>a>>b;
	init(a,b);
	// for(auto i:v){
	// 	for(int j:i)cout<<j<<" ";
	// 	cout<<endl;
	// }
	for(int i=0;i<q;i++){
		int x,y;cin>>x>>y;
		cout<<get_distance(x,y)<<endl;
	}
}