| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 690957 | 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;
ll n,q,zer=0;
ll TreeD[4*sz];
string a,b;
void builD(ll v, ll l, ll r){
if(l==r){
if(a[l]!=b[l]){
TreeD[v]=1;return;
}
TreeD[v]=0;return;
}
ll m=(l+r)>>1;
builD(v*2,l,m);
builD(v*2+1,m+1,r);
TreeD[v]=TreeD[v*2]+TreeD[v*2+1];
}
int FinD(ll v, ll tl, ll tr, ll l, ll r){
if(l>r){
return 0;
}
if(tl==l and tr==r){
return TreeD[v];
}
ll tm=(tl+tr)>>1;
return FinD(v*2,tl,tm,l,min(r,tm))+FinD(v*2+1,tm+1,tr,max(l,tm+1),r);
}
int get_distance(ll left, ll right){
int rx=FinD(1,0,n-1,left,right);
int res=(rx/2)+(rx%2);
return max(res,zer);
}
void init(string a, string b){
builD(1,0,n-1);
vl ac,aa,at,bc,ba,bt;
for(ll i=0;i<n;i++){
if(a[i]=='C'){
ac.pb(i);
}
else if(a[i]=='A'){
aa.pb(i);
}
else{
at.pb(i);
}
if(b[i]=='C'){
bc.pb(i);
}
else if(b[i]=='A'){
ba.pb(i);
}
else{
bt.pb(i);
}
}
while(q--){
ll left, right;
cin>>left>>right;
ll lac=lower_bound(ac.begin(),ac.end(),left)-ac.begin();
ll uac=upper_bound(ac.begin(),ac.end(),right)-ac.begin();//uac=max(zer,uac);
if(ac[uac-1]>right){uac--;}uac=max(zer,uac);
ll cntac=uac-lac;
cntac=max(cntac,zer);
ll laa=lower_bound(aa.begin(),aa.end(),left)-aa.begin();
ll uaa=upper_bound(aa.begin(),aa.end(),right)-aa.begin();//uaa=max(zer,uaa);
if(aa[uaa-1]>right){uaa--;}uaa=max(zer,uaa);
ll cntaa=uaa-laa;
cntaa=max(cntaa,zer);
ll lat=lower_bound(at.begin(),at.end(),left)-at.begin();
ll uat=upper_bound(at.begin(),at.end(),right)-at.begin();//uat=max(zer,uat);
if(at[uat-1]>right){uat--;}uat=max(zer,uat);
ll cntat=uat-lat;
cntat=max(cntat,zer);
/*##############################################*/
ll lbc=lower_bound(bc.begin(),bc.end(),left)-bc.begin();
ll ubc=upper_bound(bc.begin(),bc.end(),right)-bc.begin();//ubc=max(zer,ubc);
if(ac[ubc-1]>right){ubc--;}ubc=max(zer,ubc);
ll cntbc=ubc-lbc;
cntbc=max(cntbc,zer);
ll lba=lower_bound(ba.begin(),ba.end(),left)-ba.begin();
ll uba=upper_bound(ba.begin(),ba.end(),right)-ba.begin();//uba=max(zer,uba);
if(ba[uba-1]>right){uba--;}uba=max(zer,uba);
ll cntba=uba-lba;
cntba=max(cntba,zer);
ll lbt=lower_bound(bt.begin(),bt.end(),left)-bt.begin();
ll ubt=upper_bound(bt.begin(),bt.end(),right)-bt.begin();//ubt=max(zer,ubt);
if(bt[ubt-1]>right){ubt--;}ubt=max(zer,ubt);
ll cntbt=ubt-lbt;
cntbt=max(cntbt,zer);
if(cntac!=cntbc or cntaa!=cntba or cntat!=cntbt){
cout<<-1<<endl;
}
else{
cout<<get_distance(left,right)<<endl;
}
}
}