HMAPPY1 - EDITORIAL

Well, that’s the alternate Implementation.

@taran_1407 Yes, and I mentioned it here in case anyone reviewing my code wonders where it happens.

I think there’s a slight mistake. the vector should be 3 -4 2 as I guess. Nice solution.

Glad you found it useful

Please explain the time complexity of buiding the tree. I have read that time complexity of building a tree is O(n). Why are you multiplying with log(n). I don’t understand why I am getting TLE as I am using segment trees.

#include <bits/stdc++.h>
using namespace std;

#define speedup ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define N 200010
#define M 800040
int A[N],tree[M],p[M],s[M];
bool z[M]={0};

int max(int a,int b,int c){
if(a>=b && a>=c)
return a;
else if(b>=a && b>=c)
return b;
else if(c>=a && c>=b)
return c;
}

void buildtree(int node,int l,int r){

if(l==r){
    tree[node]=A[l];
    if(A[l])
        p[node]=s[node]=1;
    else{
        p[node]=s[node]=0;
        z[node]=1;
    }
    
    return;
}

int mid=(l+r)/2;
//mid>>1;
buildtree(2*node+1,l,mid);
buildtree(2*node+2,mid+1,r);
if(!z[2*node+1] && !z[2*node+2])
    tree[node]=p[node]=s[node]=p[2*node+1]+s[2*node+2];
else if(z[2*node+1] && !z[2*node+2]){
    p[node]=p[2*node+1];
    s[node]=s[2*node+1]+s[2*node+2];
    tree[node]=max(tree[2*node+1],tree[2*node+2],s[node]);
    z[node]=1;
}
else if(!z[2*node+1] && z[2*node+2]){
    s[node]=s[2*node+2];
    p[node]=p[2*node+1]+p[2*node+2];
    tree[node]=max(tree[2*node+1],tree[2*node+2],p[node]);
    z[node]=1;
}
else{
    p[node]=p[2*node+1];
    s[node]=s[2*node+2];
    tree[node]=max(tree[2*node+1],tree[2*node+2],p[node]+s[node]);
    z[node]=1;
}

}

int main() {
// your code goes here
speedup;
int n,k,q;
cin>>n>>k>>q;
for(int i=0;i<n;i++){
cin>>A[i];
A[i+n]=A[i];
}
string s;
cin>>s;
//buildtree(0,0,n-1);
int shift=0,f=1;
for(int i=0;i<s.length();i++){
if(s[i]==’?’){
if(f){
buildtree(0,n-shift,2*n-1-shift);
f=0;
}
if(tree[0]>k)
cout<<k<<endl;
else
cout<<tree[0]<<endl;
}
else{
f=1;
shift++;
shift=shift%n;
}
}
return 0;
}

Can anyone provide the C++ solution with segment tree?

https://www.codechef.com/viewsolution/26143670
Please help…Why am I getting a WA ? Please give a test case that my code is failing

7 28 2
1 1 0 0 0 0 0 
?!?!?!?!?!?!?!?!?!?!?!?!?!?!
1 Like