Need help with Chefs in Queue

1

Problem name: Chefs in Queue
Problem link: CHFQUEUE Problem - 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;
}
2

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

Accepted

3

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

4

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

5

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

6

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