Shinchan and Kazama

QUESTION

Shinchan and Kazama both are playing with numbers. Shinchan gives Kazama an array of numbers and asks him to tell the minimum possible last number of a non decreasing sequence of length L\nNote- Check the sample I/O for more clarity.\n\nINPUT-\nEach test case contains size of array i.e N. Next line contains N space separated elements of array. Next line contains length of the non decreasing sequence i.e. L\n\nOUTPUT- \nYou have to print the minimum possible last number of a sequence and if their is no non-decreasing sequence of length L, then print \”1\” without the quotes.

“TESTCASE_1”: “7\n9 7 2 5 4 11 12 \n3\n###—###SEPERATOR—###—\n11”, “TESTCASE_2”: “2\n33 73 \n1\n###—###SEPERATOR—###—\n33”, “TESTCASE_3”: “14\n72 70 29 77 73 97 12 86 90 61 36 55 67 55 \n7\n###—###SEPERATOR—###—\n-1”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
 
int main(){
    
     long n,l,x;
  
        vector<long> st(100005,0);
        
        int top=0;
        st[0]=-1;
        cin>>n;
        for(int i=0;i<n;i++){
        cin>>x;
        if(x>st[top])
        st[++top]=x;
        
        else{
        long l=1,r=top,mid;
        while(l<=r){
            long mid=(l+r)/2;
            if(st[mid]<x){
                l=mid+1;
            }
            else
            r=mid-1;
        }
        st[l]=x;
        }
        
        }
        cin>>l;
        if(top<l)
        cout<<"-1\n";
        else
        cout<<st[l]<<"\n";
    
    return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro