| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1339383 | rafiqshaid | DNA 돌연변이 (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define YN(ans) ans?cout<<"YES"<<endl:cout<<"NO"<<endl;
#define vin(a,n) vector<int>a(n);for(auto &x:a)cin>>x;
#define st(v,x) x==0?sort(v.begin(),v.end()):sort(v.rbegin() , v.rend());
#define vout(a) for(auto x:a){cout<<x<<' ';}cout<<"\n";
#define all(a) a.begin(), a.end()
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cerr << vars << " = ";
string delim = "";
(..., (cerr << delim << values, delim = ", "));
cerr << endl;
}
const int mod=1e9+7,N=2e6+7;
void solved(){
int n, q;
string a, b;
cin >> n >> q >> a >> b;
vector<int>va[3], vb[3];
for(int i = 0; i < 3; i++) {
va[i].resize(n+1);
vb[i].resize(n+1);
}
vector<int>at(n+1, 0), ta(n+1, 0), equal(n+1, 0);
unordered_map<char, int>mp;
mp['A'] = 0;
mp['C'] = 1;
mp['T'] = 2;
for(int i = 0; i<n; i++){
char ch = a[i];
char ch1 = b[i];
for(int j = 0; j<3; j++){
va[j][i+1] = va[j][i];
vb[j][i+1] = vb[j][i];
}
va[mp[ch]][i+1]++;
vb[mp[ch1]][i+1]++;
at[i+1] = at[i];
ta[i+1] = ta[i];
equal[i+1] = equal[i];
if(ch == 'A' and ch1 == 'T')at[i+1]++;
if(ch1 == 'A' and ch == 'T')ta[i+1]++;
if(ch == ch1)equal[i+1]++;
}
while(q--){
int x, y;
cin >> x >> y;
int total = y - x + 1;
int same = equal[y+1] - equal[x];
total -= same;
for(int i = 0; i<3; i++){
if(va[i][y+1] - va[i][x] != vb[i][y+1] - vb[i][x]){
cout << -1 << endl;
return;
}
}
int a_t = at[y+1] - at[x];
int t_a = ta[y+1] - ta[x];
int ans = abs(a_t - t_a);
total -= 3*ans;
ans *= 2;
ans += total/2;
cout << ans << endl;
}
}
signed main(){
fastio
int test_case=1,n=1;//cin>>test_case;
while (test_case--){
solved();
}
}