| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1265152 | tcmduc | Mutating DNA (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const long long oo=1e18;
const int mod=1e9+7;
void home()
{
freopen("main.inp","r",stdin);
freopen("main.out","w",stdout);
}
bool bit(int x,int i){return (x>>i)&1;}
int n,q;
string a,b;
int cnt[3][100005][4],dif[100005][4][4];
void init(string a,string b)
{
a='0'+a,b='0'+b;
for(int i=1;i<=n;i++)
{
if(a[i]=='A')a[i]='1';if(a[i]=='C')a[i]='2';if(a[i]=='T')a[i]='3';
if(b[i]=='A')b[i]='1';if(b[i]=='C')b[i]='2';if(b[i]=='T')b[i]='3';
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=2;j++)for(int k=1;k<=3;k++)cnt[j][i][k]=cnt[j][i-1][k];
cnt[1][i][a[i]-'0']++;
cnt[2][i][b[i]-'0']++;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=3;j++)for(int k=1;k<=3;k++)dif[i][j][k]=dif[i-1][j][k];
dif[i][a[i]-'0'][b[i]-'0']++;
}
}
int get_distance(int x,int y)
{
x++,y++;
for(int i=1;i<=3;i++)
if(cnt[1][y][i]-cnt[1][x-1][i]!=cnt[2][y][i]-cnt[2][x-1][i])return -1;
int kq=0,thua=0;
for(int i=1;i<=3;i++)
{
for(int j=i+1;j<=3;j++)
{
int d1=dif[y][i][j]-dif[x-1][i][j];
int d2=dif[y][j][i]-dif[x-1][j][i];
kq+=min(d1,d2);
thua+=max(d1,d2)-min(d1,d2);
}
}
return kq+thua/3*2;
}
void Tcmduc_VOI26()
{
cin>>n>>q>>a>>b;
init(a,b);
while(q--)
{
int x,y;cin>>x>>y;
cout<<get_distance(x,y)<<'\n';
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);//home();
Tcmduc_VOI26();
return 0;
}