제출 #690943

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
690943		vjudge1	DNA 돌연변이 (IOI21_dna)	C++17	0 / 100	1191 ms	2097156 KiB

dna

#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];
}
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(int left, int 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;
        }
    }
}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 22
• Subtask 3: 0 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16