HackerRank Super Kth LIS problem solution

In this HackerRank Super Kth LIS problem solution, we have given an array of N integers and we need to find all possible increasing subsequences of maximum length L. then we need to print the lexicographically Kth longest increasing subsequences as a single line of space-separated integers and if there are less than K subsequences of length L then print -1.

Problem solution in Java.

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;

public class E {
    InputStream is;
    PrintWriter out;
    String INPUT = "";
    
    static long I = 2000000000_000000000L;
    
    void solve()
    {
        int n = ni();
        long K = nl();
        int[] a = na(n);
        int[] b = Arrays.copyOf(a, n);
        for(int i = 0;i < n;i++)b[i] = n-a[n-1-i];
        b = shrink(b);

        
        SegmentTreeRMQSumWhenMax st = new SegmentTreeRMQSumWhenMax(n+5);
        st.updateOrAdd(0, 0, 1); 
        int[] maxs = new int[n+1];
        long[] counts = new long[n+1];
        double[] cx = new double[n+1];
        for(int i = 0;i < n;i++){
            int max = st.maxx(0, b[i]+1); 
            maxs[i] = max;
            if(st.gwd >= I)st.gw = I;
            counts[i] = st.gw;
            cx[i] = st.gwd;
            st.updateOrAdd(b[i]+1, max+1, st.gw);
        }
        int max = st.maxx(0, n+1);
        maxs[n] = max;
        counts[n] = st.gw;
        cx[n] = st.gwd;
        if(cx[n] <= 2E18 && K > counts[n]){
            out.println(-1);
            return;
        }
        int lis = maxs[n];
        int[][] g = makeBuckets(maxs, lis);
        for(int i = 0;i < n+1;i++){
            if(cx[i] >= 2E18){
                counts[i] = I;
            }
        }
        
        long[] ft = new long[n+3];
        double[] ftd = new double[n+3];
        addFenwick(ft, 0, 1);
        addFenwick(ftd, 0, 1);
        int[] ret = new int[lis];
        int[] prevs = new int[n];
        long[] pvs = new long[n];
        int pp = 0;
        prevs[pp] = 0; pvs[pp] = 1; pp++;
        for(int h = lis-1;h >= 0;h--){
            long[][] temps = new long[g[h].length][];
            int p = 0;
            for(int i : g[h]){
                int ind = n-1-i;
                if(h < lis-1 && a[ind] <= ret[lis-(h+1)-1])continue;
                long sum = sumFenwick(ft, ind+1);
                double sumd = sumFenwick(ftd, ind+1);
                if(sumd >= I)sum = I;
                long cc = sum*counts[i];
                double cd = (double)counts[i]*sum;
                if(cd > 2E18){
                    cc = I;
                }
                temps[p++] = new long[]{a[ind], cc, sum, ind+1};
            }
            for(int j = 0;j < pp;j++){
                addFenwick(ft, prevs[j], -pvs[j]);
                addFenwick(ftd, prevs[j], -pvs[j]);
            }
            
            
            Arrays.sort(temps, 0, p, new Comparator<long[]>() {
                public int compare(long[] a, long[] b) {
                    return Long.compare(a[0], b[0]);
                }
            });

            for(int i = 0;i < p;){
                int j = i;
                while(j < p && temps[j][0] == temps[i][0])j++;
                long lnum = 0;
                for(int k = i;k < j;k++){
                    lnum += temps[k][1];
                    if(lnum >= I)lnum = I;
                }
                if(K - lnum <= 0){
                    ret[lis-h-1] = (int)temps[i][0];
                    break;
                }else{
                    K -= lnum;
                }
                i = j;
            }
            pp = 0;
            for(int i = 0;i < p;i++){
                long[] t = temps[i];
                if(t[0] == ret[lis-h-1]){

                    addFenwick(ft, (int)t[3], t[2]);
                    addFenwick(ftd, (int)t[3], t[2]);
                    prevs[pp] = (int)t[3]; pvs[pp] = t[2]; pp++;
                }
            }
        }

        for(int i = 0;i < lis;i++){
            out.print(ret[i] + " ");
        }
        out.println();
    }
    
    public static long sumFenwick(long[] ft, int i)
    {
        long sum = 0;
        for(i++;i > 0;i -= i&-i){
            sum += ft[i];
        }
        return sum;
    }
    
    public static void addFenwick(long[] ft, int i, long v)
    {
        if(v == 0)return;
        int n = ft.length;
        for(i++;i < n;i += i&-i)ft[i] += v;
    }

    public static double sumFenwick(double[] ft, int i)
    {
        double sum = 0;
        for(i++;i > 0;i -= i&-i){
            sum += ft[i];
        }
        return sum;
    }
    
    public static void addFenwick(double[] ft, int i, double v)
    {
        if(v == 0)return;
        int n = ft.length;
        for(i++;i < n;i += i&-i)ft[i] += v;
    }

    
    public static int[][] makeBuckets(int[] a, int sup)
    {
        int n = a.length;
        int[][] bucket = new int[sup+1][];
        int[] bp = new int[sup+1];
        for(int i = 0;i < n;i++)bp[a[i]]++;
        for(int i = 0;i <= sup;i++)bucket[i] = new int[bp[i]];
        for(int i = n-1;i >= 0;i--)bucket[a[i]][--bp[a[i]]] = i;
        return bucket;
    }

    
    public static int[] shrink(int[] a) {
        int n = a.length;
        long[] b = new long[n];
        for (int i = 0; i < n; i++)
            b[i] = (long) a[i] << 32 | i;
        Arrays.sort(b);
        int[] ret = new int[n];
        int p = 0;
        for (int i = 0; i < n; i++) {
            if (i > 0 && (b[i] ^ b[i - 1]) >> 32 != 0)
                p++;
            ret[(int) b[i]] = p;
        }
        return ret;
    }
    
    private static class SegmentTreeRMQSumWhenMax {
        public int M, H, N;
        public int[] st;
        public long[] w;
        public double[] wd;
        
        public SegmentTreeRMQSumWhenMax(int n)
        {
            N = n;
            M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
            H = M>>>1;
            st = new int[M];
            w = new long[M];
            wd = new double[M];
            Arrays.fill(st, 0, M, Integer.MIN_VALUE);
        }
        
       
        public void updateOrAdd(int pos, int x, long y)
        {
            if(x < st[H+pos])throw new RuntimeException("x < st[H+pos]");
            if(x == st[H+pos]){
                w[H+pos] += y;
                wd[H+pos] += y;
            }else{
                st[H+pos] = x;
                w[H+pos] = y; 
                wd[H+pos] = y;
            }
            for(int i = (H+pos)>>>1;i >= 1;i >>>= 1)propagate(i);
        }
        
        private void propagate(int i)
        {
            if(st[2*i] < st[2*i+1]){
                st[i] = st[2*i+1];
                w[i] = w[2*i+1];
                wd[i] = wd[2*i+1];
            }else if(st[2*i] > st[2*i+1]){
                st[i] = st[2*i];
                w[i] = w[2*i];
                wd[i] = wd[2*i];
            }else{
                st[i] = st[2*i];
                w[i] = w[2*i] + w[2*i+1];
                wd[i] = wd[2*i] + wd[2*i+1];
            }
        }
        
        public long gw;
        public double gwd;
        
        public int maxx(int l, int r){
            gw = 0;
            gwd = 0.;
            if(l >= r)return 0;
            int max = Integer.MIN_VALUE;
            while(l != 0){
                int f = l&-l;
                if(l+f > r)break;
                int v = st[(H+l)/f];
                if(v > max){
                    max = v;
                    gw = w[(H+l)/f];
                    gwd = wd[(H+l)/f];
                }else if(v == max){
                    gw += w[(H+l)/f];
                    gwd += wd[(H+l)/f];
                }
                l += f;
            }
            
            while(l < r){
                int f = r&-r;
                int v = st[(H+r)/f-1];
                if(v > max){
                    max = v;
                    gw = w[(H+r)/f-1];
                    gwd = wd[(H+r)/f-1];
                }else if(v == max){
                    gw += w[(H+r)/f-1];
                    gwd += wd[(H+r)/f-1];
                }
                r -= f;
            }
            return max;
        }
    }
    
    void run() throws Exception
    {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
    }
    
    public static void main(String[] args) throws Exception { new E().run(); }
    
    private byte[] inbuf = new byte[1024];
    private int lenbuf = 0, ptrbuf = 0;
    
    private int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ 
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

Problem solution in C++.

#include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 2234567890123456789ULL
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;


#ifdef DONLINE_JUDGE
    #define lld I64d
#endif

unsigned long long pw(unsigned long long a, unsigned long long e, unsigned long long mod) {
    if(e <= 0) return 1;
    unsigned long long x =pw(a,e/2,mod);
    x =(x*x)%mod;
    if(e%2 != 0) x =(x*a)%mod;
    return x;}

struct fins {
    vector<unsigned long long> T;
    fins() {}
    fins(int N) {T.resize(N,0);}

    int lastone(int x) {return x&(x^(x-1));}

    void put(int pos, unsigned long long val) {
        for(int i =pos+1; i < (int)T.size(); i +=lastone(i)) T[i] =min(OVER9000,T[i]+val);
        }

    unsigned long long get(int pos) {
        unsigned long long ret =0;
        for(int i =pos+1; i > 0; i -=lastone(i)) ret =min(OVER9000,ret+T[i]);
        return ret;}
    };

struct finm {
    vector<unsigned long long> T;
    finm(int N) {T.resize(N,0);}

    int lastone(int x) {return x&(x^(x-1));}

    void put(int pos, unsigned long long val) {
        for(int i =pos+1; i < (int)T.size(); i +=lastone(i)) T[i] =max(T[i],val);
        }

    void clr(int pos) {
        for(int i =pos+1; i < (int)T.size(); i +=lastone(i)) T[i] =0;}

    unsigned long long get(int pos) {
        unsigned long long ret =0;
        for(int i =pos+1; i > 0; i -=lastone(i)) ret =max(ret,T[i]);
        return ret;}
    };

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(10);
    int N;
    unsigned long long K;
    cin >> N >> K;
    vector<int> A(N);
    map<int, vector<int> > pos;
    for(int i =0; i < N; i++) {
        cin >> A[i];
        pos[A[i]].push_back(i);}

    vector<int> len(N,0);
    vector<unsigned long long> poc(N,0);
    finm lisF(N+tisic);
    int L =0;
    vector<int> V(N+tisic,0);
    for(int i =N-1; i >= 0; i--) {
        len[i] =lisF.get(N-A[i])+1;
        L =max(L,len[i]);
        V[len[i]]++;
        lisF.put(N-A[i]+1,len[i]);}
    vector< map<int,unsigned long long> > lisMs(L+1);
    lisMs[0][0] =1;
    vector<fins> lisFs(L+1);
    for(int i =0; i <= L; i++) if(V[i] > 50) {
        lisFs[i] =fins(N+tisic);
        if(i < L) lisFs[i+1] =fins(N+tisic);
        if(i > 0) lisFs[i-1] =fins(N+tisic);}
    lisFs[0] =fins(N+tisic);
    lisFs[0].put(0,1);
    for(int i =N-1; i >= 0; i--) {
        if(V[len[i]-1] > 50) poc[i] =lisFs[len[i]-1].get(N-A[i]);
        else {
            auto it =lisMs[len[i]-1].upper_bound(N-A[i]);
            for(auto jt =lisMs[len[i]-1].begin(); jt != it; jt++) poc[i] =min(OVER9000,poc[i]+jt->ss);}
        if(V[len[i]] > 50)
            lisFs[len[i]].put(N-A[i]+1,poc[i]);
        else 
            lisMs[len[i]][N-A[i]+1] +=poc[i];
        }

    vector<unsigned long long> prev_len(N+1,0), prev_poc(N+1,0);
    prev_poc[0] =1;
    vector<int> ans(L);
    int Lcur =0;
    finm F(N+tisic);
    fins Fp(N+tisic);
    Fp.put(0,1);
    vector<int> sofar(1,0);
    ALL_THE(pos,it) {
        vector<int> v =it->ss;
        unsigned long long k2 =0;
        ALL_THE(v,jt) {
            prev_len[*jt+1] =F.get(*jt)+1;
            if(len[*jt]+prev_len[*jt+1]-1 != L) continue;
            prev_poc[*jt+1] =Fp.get(*jt);
            if(poc[*jt] == 0 || OVER9000/poc[*jt] > prev_poc[*jt+1])
                k2 =min(OVER9000,k2+prev_poc[*jt+1]*poc[*jt]);
            else k2 =OVER9000;}
        if(k2 >= K) {
            ans[Lcur] =it->ff;
            ALL_THE(sofar,jt) {
                Fp.put(*jt,-prev_poc[*jt]);
                F.clr(*jt);
                prev_len[*jt] =prev_poc[*jt] =0;}
            Lcur++;}
        else K -=k2;
        ALL_THE(v,jt) if(prev_len[*jt+1] == Lcur) {
            sofar.push_back(*jt+1);
            F.put(*jt+1,prev_len[*jt+1]);
            Fp.put(*jt+1,prev_poc[*jt+1]);}
        }

    if(Lcur < L) cout << "-1\n";
    else for(int i =0; i < L; i++) cout << ans[i] << ((i == L-1)?"\n":" ");
    return 0;}