| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1190877 | vyaduct | Mutating DNA (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const long double EPS = 1e-9;
void file(){
freopen("input.txt.txt","r",stdin);
freopen("output.txt.txt","w",stdout);
}
#define V vector
#define pb push_back
#define P pair
#define S second
#define F first
#define all(v) v.begin(),v.end()
int pref[(int)1e5+1][2][3];
int pref2[(int)1e5+1][6];
void init(string a,string b){
a='.'+a;
b='.'+b;
int n=(int)a.length();
for(int i=0;i<2;i++){
for(int j=0;j<3;j++){
pref[0][i][j]=0;
}
}
for(int i=0;i<6;i++){
pref2[0][i]=0;
}
V<char>vp={'A','T','C'};
V<P<char,char>>vp1={{'A','T'},{'T','A'},{'A','C'},{'C','A'},{'C','T'},{'T','C'}};
for(int i=1;i<=n;i++){
for(int j=0;j<3;j++){
pref[i][0][j]=pref[i-1][0][j];
pref[i][1][j]=pref[i-1][1][j];
if(a[i]==vp[j])pref[i][0][j]++;
if(b[i]==vp[j])pref[i][1][j]++;
}
for(int j=0;j<6;j++){
pref2[i][j]=pref2[i-1][j];
if(a[i]==vp1[j].F && b[i]==vp1[j].S)pref2[i][j]++;
}
}
}
int get_distance(int x, int y){
x++,y++;
for(int i=0;i<3;i++){
if(pref[y][0][i]-pref[x-1][0][i]!=pref[y][1][i]-pref[x-1][1][i])return -1;
}
int cnt1=0;
int cnt2=0;
for(int i=0;i<6;i+=2){
int mind=min(pref2[y][i]-pref2[x-1][i],pref2[y][i+1]-pref2[x-1][i+1]);
int maxd=max(pref2[y][i]-pref2[x-1][i],pref2[y][i+1]-pref2[x-1][i+1]);
cnt1+=mind;
cnt2+=maxd-mind;
}
return cnt1+((2*cnt2)/3);
}
void solve() {
int n,q;
cin>>n>>q;
string a,b;
cin>>a>>b;
init(a,b);
while(q--){
int x,y;
cin>>x>>y;
cout<<get_distance(x,y)<<endl;
}
}
int main(){
// file();
solve();
return 0;
}