Well, that’s the alternate Implementation.
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
do you have solution of above problem now?
As i am stuck with same problem