Submission #476406

#	Time	Username	Problem	Language	Result	Execution time	Memory
476406		Mahmudul_Kabir	Mutating DNA (IOI21_dna)	C++17	56 / 100	87 ms	11648 KiB

dna

//#include "dna.h"

#include "bits/stdc++.h"

#define sp <<" "
#define el <<"\n"
#define S second
#define F first
#define pb push_back
#define all(ar) ar.begin(),ar.end() 
#define pii pair<int,int> 

 
using namespace std;
using ll = long long; 
using ld = long double;
 
const int mod = 100000007;
const int si = 100005;
const int inf = 7000; 

ll po[si][3], pt[si][3],n; 
unordered_map<char,ll> hau = {{'A',0},{'T',1},{'C',2}}; 
ll str[si * 4]; 

void make(int x,int y,int node,string &a,string &b){
    if(x == y){
        str[node] = a[x] == b[x]; 
        return; 
    }
    int mid = x + (y - x)/2, lef = node * 2; 
    make(x,mid,lef,a,b); make(mid+1,y,lef + 1,a,b); 
    str[node] = str[lef] + str[lef+1]; 
    return; 
}

int que(int a,int b,int l,int r,int node){
    if(b < l || r < a) return 0; 
    if(a >= l && r >= b) return str[node]; 
    int mid = a + (b - a)/2, lef = node * 2; 
    return que(a,mid,l,r,lef) + que(mid+1,b,l,r,lef+1);  
}


void init(std::string a, std::string b){
    n = a.size(); 
    memset(po,0,sizeof(po)); memset(pt,0,sizeof(pt)); 
    po[0][hau[a[0]]] += 1; pt[0][hau[b[0]]] += 1; 
    for(int i = 1; i < n; i++){
        for(int j = 0; j < 3; j++){
            po[i][j] = po[i - 1][j]; 
            pt[i][j] = pt[i - 1][j];
        }
        po[i][hau[a[i]]] += 1;
        pt[i][hau[b[i]]] += 1; 
    }
    memset(str,0,sizeof(str)); 
    make(0,n-1,1,a,b); 
    return; 
}

int get(int x,int y,int i,bool t){
    ll ans = t ? pt[y][i] : po[y][i]; 
    if(x) ans -= t ? pt[x - 1][i] : po[x - 1][i]; 
    return ans;  
}

bool hobe(int x,int y){
    //cout<<get(x,y,0,0) sp<< get(x,y,0,1) sp<<get(x,y,1,0) sp<< get(x,y,1,1) sp<<get(x,y,2,0) sp<< get(x,y,2,1) el; 
    return (get(x,y,0,0) == get(x,y,0,1)) && (get(x,y,1,0) == get(x,y,1,1)) && (get(x,y,2,0) == get(x,y,2,1)); 
}

int get_distance(int x, int y) {
    if(!hobe(x,y)) return -1; 
    return (y - x - que(0,n - 1,x,y,1) + 2)/2;
}

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