| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 991652 | wood | 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 "dna.h"
#include <cstdio>
#include <cassert>
#include <string>
#include <vector>
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay
using t = tuple<int,int,int>;
vi pa[3], pb[3];
vi res;
void init(std::string a, std::string b) {
char cc[3] = {'A', 'C', 'T'};
int n = a.size();
for(int i = 0; i<3; i++){
pa[i].resize(n+1);
pb[i].resize(n+1);
}
res.resize(n+1);
for(int i = 0; i<n; i++){
for(int j = 0; j<3; j++){
pa[j][i+1] = pa[j][i] + (a[i] == cc[j]);
pb[j][i+1] = pb[j][i] + (b[i] == cc[j]);
}
res[i+1] = res[i]+
(a[i]=='A'&&b[i]!='A')+
(a[i]=='C'&&b[i]=='T');
}
}
int get_distance(int x, int y) {
for(int i = 0; i<3; i++){
if(pa[i][y+1]-pa[i][x]!=pb[i][y+1]-pb[i][x]) return -1;
}
return res[y+1]-res[x];
}
int main() {
#ifdef _WIN32
freopen("input.in", "r", stdin);
freopen("input.out", "w", stdout);
#endif
int n, q;
cin>>n>>q;
string a,b; cin>>a>>b;
std::vector<int> x(q), y(q);
for (int i = 0; i < q; i++) {
cin>>x[i]>>y[i];
}
fclose(stdin);
std::vector<int> results(q);
init(a, b);
for (int i = 0; i < q; i++) {
results[i] = get_distance(x[i], y[i]);
}
for (int i = 0; i < q; i++) {
cout<<results[i]<<'\n';
}
fclose(stdout);
return 0;
}