| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 690941 | vjudge1 | DNA 돌연변이 (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
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];
}
ll 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);
}
ll get_distance(ll left, ll right){
ll rx=FinD(1,0,n-1,left,right)-1;
return max(rx,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();
if(ac[uac-1]>right){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();
if(aa[uaa-1]>right){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();
if(at[uat-1]>right){uac--;}
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();
if(ac[ubc-1]>right){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();
if(ba[uba-1]>right){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();
if(bt[ubt-1]>right){ubc--;}
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;
}
}
}
int main(){
cin>>n>>q;
//string a,b;
cin>>a>>b;
init(a,b);
}