| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1298034 | tit_manh | Mutating DNA (IOI21_dna) | C++20 | 0 ms | 0 KiB |
/*
author : TIT_manh
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <numeric>
#include <functional>
#include <cassert>
#include <sstream>
#include <climits>
#define ll long long
#define FOR(i,l,r) for (int i = l; i <= r; i++)
#define FOD(i,r,l) for (int i = r; i >= l; i--)
#define fi first
#define se second
#define pb push_back
#define endl "\n"
using namespace std;
const int maxn = 1e5 + 5;
int n, q, pre1[3][maxn], pre2[3][maxn], p[maxn];
int get_distance(int x, int y) {
FOR(i,0,2) {
if (x == 0) {
if (pre1[i][y] != pre2[i][y]) return -1;
}
else if (pre1[i][y] - pre1[i][x - 1] != pre2[i][y] - pre2[i][x - 1]) return -1;
}
if (x == 0) {
return (p[y] / 2) + (p[y] % 2);
}
else return ((p[y] - p[x - 1]) / 2) + ((p[y] - p[x - 1]) % 2);
}
void init(string a, string b) {
FOR(i,0,n-1) {
if (i != 0) p[i] = p[i - 1];
if (a[i] != b[i]) {
p[i]++;
}
if (a[i] == 'A') {
pre1[0][i] = 1;
}
if (a[i] == 'C') {
pre1[1][i] = 1;
}
if (a[i] == 'T') {
pre1[2][i] = 1;
}
if (b[i] == 'A') {
pre2[0][i] = 1;
}
if (b[i] == 'C') {
pre2[1][i] = 1;
}
if (b[i] == 'T') {
pre2[2][i] = 1;
}
if (i != 0) {
pre1[0][i] += pre1[0][i - 1];
pre1[1][i] += pre1[1][i - 1];
pre1[2][i] += pre1[2][i - 1];
pre2[0][i] += pre2[0][i - 1];
pre2[1][i] += pre2[1][i - 1];
pre2[2][i] += pre2[2][i - 1];
}
}
while (q--) {
int x, y; cin >> x >> y;
cout << get_distance(x, y) << endl;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> q;
string a, b; cin >> a >> b;
init(a, b);
return 0;
}