# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
494039 | Tsiannis | Mutating DNA (IOI21_dna) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 100005
ll a1[maxn],c1[maxn],t1[maxn],a2[maxn],c2[maxn],t2[maxn],diff[maxn];
void init(string a,string b)
{
int n=a.size();
for (int i=0;i<n;i++)
{
a1[i+1]=a1[i];
c1[i+1]=c1[i];
t1[i+1]=t1[i];
a2[i+1]=a2[i];
c2[i+1]=c2[i];
t2[i+1]=t2[i];
diff[i+1]=diff[i];
if (a[i]=='A')
a1[i+1]=a1[i]+1;
else if (a[i]=='C')
c1[i+1]=c1[i]+1;
else
t1[i+1]=t1[i]+1;
if (b[i]=='A')
a2[i+1]=a2[i]+1;
else if (b[i]=='C')
c2[i+1]=c2[i]+1;
else
t2[i+1]=t2[i]+1;
if (a[i]!=b[i])
{diff[i+1]=diff[i]+1;}
}
}
int get_distance(int x,int y)
{
int pla1=a1[y+1]-a1[x];
int plc1=c1[y+1]-c1[x];
int plt1=t1[y+1]-t1[x];
int pla2=a2[y+1]-a2[x];
int plc2=c2[y+1]-c2[x];
int plt2=t2[y+1]-t2[x];
int d=diff[y+1]-diff[x];
if (pla1!=pla2||plc1!=plc2||plt1!=plt2)
return -1;
else
return (d/2+d%2);
}
int main()
{
int n,q;
cin>>n>>q;
string s1,s2;
cin>>s1>>s2;
init(s1,s2);
while(q--)
{
int x,y;
cin>>x>>y;
cout<<get_distance(x,y)<<endl;
}
return 0;
}