Submission #691663

#	Time	Username	Problem	Language	Result	Execution time	Memory
691663		vjudge1	DNA 돌연변이 (IOI21_dna)	C++17	0 / 100	30 ms	4896 KiB

dna

#include <bits/stdc++.h>
#define ll int
#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 ;
}
/*
int main(){
    ll l, r;
    cin>>n>>q;
    string a,b;
    cin>>a>>b;
    init(a,b);
    while(q--){
            cin>>l>>r;
        cout<<get_distance(l,r)<<endl;
    }
}


*/

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