 # Need help with Chefs in Queue

Problem name: Chefs in Queue
Problem link: Contest Page | CodeChef

I have solved it using the stack-based approach but now I want to solve it with the segment-tree based approach.
I have the consider the the values of a[i] as 0-based for my convinience in the segment tree.
The logic is to traverse from right to left in the given array, and put the contribution of a[i] in the segment tree as a point update.
I constructed a segment tree for the values of seniority, the root node of the current segment tree contains the minimum index for the seniority levels from 0 to k. The leaves contain the minimum index for the seniority levels 0,1,2,3,… k
The answer for each a[i], will be a range minimum query for the range 0 to a[i]-1 which will find the smallest index such that value at that index is smaller than a[i]

This code results into a WA.
But I am unable to find the issue in my thinking or code.
Can anyone help me out. Thank you in advance.

``````#include <bits/stdc++.h>
using namespace std;
#define fastio()                      \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);                    \
cout.tie(NULL);
#define lli long long int
#define ll long long
#define pii pair<int,int>

ll INF=1e18+1000;
ll mod=1e9+7;

ll find(ll idx,ll low,ll high,ll l,ll r,ll seg[])
{
if(low>high) return INF;

if(r<low || high<l) return INF;
else if(l<=low && high<=r) return seg[idx];

ll mid=(low+high)>>1;
ll res_l=find(2*idx+1,low,mid,l,r,seg);
ll res_r=find(2*idx+2,mid+1,high,l,r,seg);

return min(res_l,res_r);
}

void update(ll idx,ll low,ll high,ll i,ll val,ll seg[])
{
if(low==high)
{
seg[idx]=val;
return;
}

ll mid=(low+high)>>1;
if(i<=mid) update(2*idx+1,low,mid,i,val,seg);
else update(2*idx+2,mid+1,high,i,val,seg);

seg[idx]=min(seg[2*idx+1],seg[2*idx+2]);
}

void solve()
{
ll n,k; cin>>n>>k;
ll a[n];
for(ll i=0;i<n;i++)
{ cin>>a[i]; a[i]--; }

ll M=4*k+10;
ll seg[M];
for(ll i=0;i<M;i++) seg[i]=INF;

ll ans=1;
for(ll i=n-1;i>=0;i--)
{
ll res=INF;
if(a[i]!=0) res=find(0,0,k-1,0,a[i]-1,seg);
update(0,0,k-1,a[i],i,seg);

if(res==INF) continue;
ans*=(res-i+1);
ans%=mod;
}

cout<<ans<<'\n';

return;
}

int main()
{
fastio();
int t=1;
// cin>>t;
while(t--) solve();

return 0;
}
``````

Check the iterative segment-tree based function fixed() in lines 70-90 of the following solution that fixes the error in your code.

Accepted

But what’s the error in my code/logic.

Your code assumes that 1 <= A[i] <= K, while the problem statement mentions that 1 <= A[i] <= 1,000,000.

The problem statement guarantees only that the number of distinct values of A[i] is at most K, but A[i] can be larger than K.

Check the function other_fix() in lines 90-105 of the following code.

Accepted

Oh, Thanks a lot, I could never have found out the mistake with your help.