| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 691658 | vjudge1 | 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 <bits/stdc++.h>
#define ll long long
#define pb push_back
#define vl vector<ll>
#define endl "\n"
#define INF 0x3F3F3F3F
using namespace std;
const int sz=1e5+5;
vl pew(sz),pac(sz),pat(sz),paa(sz),pba(sz),pbc(sz),pbt(sz);
ll n,q;
ll get_distance(ll l, ll r){
ll cntac=pac[r]-pac[l-1];
ll cntbc=pbc[r]-pbc[l-1];
ll cntaa=paa[r]-paa[l-1];
ll cntba=pba[r]-pba[l-1];
ll cntat=pat[r]-pat[l-1];
ll cntbt=pbt[r]-pbt[l-1];
if(cntaa!=cntba or cntac!=cntbc or cntat!=cntbt){
return -1;
}
ll res=pew[r]-pew[l-1];
ll ans=res/2+(res%2);
return ans;
}
void init(string a, string b){
if(a[0]!=b[0]){pew[0]=0;}
if(a[0]=='A'){paa[0]=1;}
else if(a[0]=='C'){pac[0]=1;}
else{pat[0]=1;}
if(b[0]=='A'){pba[0]=1;}
else if(b[0]=='C'){pbc[0]=1;}
else{pbt[0]=1;}
for(ll i=1;i<n;i++){
if(a[i]!=b[i]){pew[i]=pew[i-1]+1;}
else{pew[i]=pew[i-1];}
if(a[i]=='A'){paa[i]=paa[i-1]+1;}
else if(a[i]=='C'){pac[i]=pac[i-1]+1;}
else{pat[i]=pat[i-1]+1;}
if(b[i]=='A'){pba[i]=pba[i-1]+1;}
else if(b[i]=='C'){pbc[i]=pbc[i-1]+1;}
else{pbt[i]=pbt[i-1]+1;}
pat[i]=max(pat[i],pat[i-1]);
pac[i]=max(pac[i],pac[i-1]);
paa[i]=max(paa[i],paa[i-1]);
pbt[i]=max(pbt[i],pbt[i-1]);
pbc[i]=max(pbc[i],pbc[i-1]);
pba[i]=max(pba[i],pba[i-1]);
}
return ;
}
/*
*/