8 weeks ago

Sahil Kumar • 260

Gurugram

Question 1 done using Segment Tree. We hold the  prefix sum upto (i-1)th index and query the segment tree for the smallest index in the range [i .....n-1] whose value is greater or equal to  prefix sum [0..i-1]+1. For more read the code below. 

//Code starts

using ll=long long int ;
 const int N=100100;
 ll a[N]; ll t[4*N];
 ll v[N];
void build (ll x,ll l,ll r) {
    if (l==r) {
       
        t[x]=a[l];
     return ;
    }
    ll mid= (l+r)/2;
    build(2*x,l,mid);
    build(2*x+1,mid+1,r);
    t[x]=t[2*x]+t[2*x+1];
    
}
void update(ll x,ll l , ll r, ll ind, ll val) {
    
    if (ind < l || ind > r) {return ;
                            }
    if (l == r) {
        t[x]=val;
        return ;
    }
    ll mid= (l+r)/2;
    update(2*x,l,mid,ind,val);
    update(2*x+1,mid+1,r,ind,val);
    t[x]=t[2*x]+t[2*x+1];
}
 ll getMin(ll x , ll l, ll r, ll lq,ll rq,ll val) {
     // finds the first index in prefix array whose value is greater than or equal to val in the range [lq,rq]
     if (lq > r || rq < l) {return -1;}
     if (l==r) {
         return t[x] >= val ? l : -1;
     }
     ll mid=(l+r)/2;
     ll temp=getMin(2*x,l,mid,lq,rq,val);
     if (temp != -1) {
         return temp;
     }
     return getMin(2*x+1,mid+1,r,lq,rq,val);
 }

int main() {
    // Approach :  lets say for any index i, j (j>=i) is the valid answer
    // Thus,   sum[i..j]>0  =>  prefix[j] - prefix[i-1] > 0
    // Therefore,  prefix[j] > prefix[i-1]  such that j is smallest in the range
    // [i.... n-1]. 
    // For every ith index we query the seg tree and cout the length of the 
    // subarray. 
    // Note in the query part I am querying  (prefix[i-1]+1) as sum should be positive so strictly greater than prefix[i-1]. My tree return >= val. So 1 is added.
    int n;
    cin>>n;
 

  
    for (int i=0;i<n;i++) {
        cin>>v[i];
   
    }
    for (int i=0;i<n;i++) {
        a[i]=v[i];
        if (i) {
            a[i]+=a[i-1];
        }
 
    }

     
     build(1,0,n-1);
  
      ll previous=0;
       for (int i=0;i<n;i++) {
       
           
        int ind=(getMin(1,0,n-1,i,n-1,previous+1));
         
          if (ind== -1) { cout<<"0"<<endl;}
 else {cout << (ind-i+1)<<endl;}
           previous+=v[i];
       }
     
    
    
}

13 months ago

SAHIL VERMA • 10

Mumbai

Vint UnEqual (int N) {
  int m=N/4;
  int count=0;
  for(int i=1;i<=m;i++){
    int sum1=(i+i);
    int sum2=N-sum1;
    if(sum2%2==0 && sum1!=sum2){
      count++;
    }
  }
  return count;
}