HackerRank Sorted Subsegments problem solution

In this HackerRank Sorted Subsegments problem solution, we have given an array of n integers and we need to sort all elements in the subsegment and print the value at index k after sorting.

Problem solution in Python.

import sys

##### Read Data
dat = [x.split() for x in sys.stdin.readlines()]
N = int(dat[0][0])
Q = int(dat[0][1])
k = int(dat[0][2])
a = list(map(int, dat[1]))
q = [list(map(int, x)) for x in dat[2:len(dat)]]

##### Process Queries
b = sorted(a)
lmin, rmax, pmax, qmin = (N-1), 0, 0, (N-1)    
pmin, qmax, flag = (N-1), 0, 1
count, span_q, ladder, revlad = [], 0, 0, 0
if Q >= 2:
    ladder = all(q[i+1][0] > q[i][0] for i in range(Q-1)) 
    revlad = all(q[i+1][1] < q[i][1] for i in range(Q-1))

if a != b and ladder < 1 and revlad < 1:
    for i in range(Q):
        l, r = q[i][0], q[i][1]       
        
        if (r-l) > (rmax-lmin):
            lmin, rmax = l, r    
        
        if l < pmin:
            pmin, pmax = l, r
        elif l == pmin and pmax < r:
            pmax = r
            
        if r > qmax:
            qmin, qmax = l, r
        elif r == qmax and qmin > l:
            qmin = l
    
    for i in range(Q):
        l, r = q[i][0], q[i][1]
        
        if l > lmin and r < rmax: continue     
        if l > pmin and r < pmax: continue             
        if l > qmin and r < qmax: continue        
        
        if i < (Q-1):
            if l >= q[i+1][0] and r <= q[i+1][1]:
                continue
            
        if i > 0:
            if l >= q[i-flag][0] and r <= q[i-flag][1]:
                flag += 1
                continue
            else:
                flag = 1

        count += [i]
        span_q += r-l+1

# Perform Queries 
if ladder > 0:
    l, r, Qu = q[0][0], q[0][1], int((k+5)/5)
    a[l:r+1] = sorted(a[l:r+1])
    for i in range(1, Q):
        l, r, r0, m, sig = q[i][0], q[i][1], q[i-1][1], 0, 0
        if l > r0 or (r-r0) > 0.1*(r0-l):
            a[l:r+1] = sorted(a[l:r+1])
            continue
        if k < l: break
        count = list(range(r0+1, r+1))
        for j in range(len(count)):
            p, new_A = count[j], a[count[j]]
            l, r0 = q[i][0], q[i-1][1]
            if a[l] >= new_A:
                del(a[p]); a[l:l] = [new_A]; continue
            elif a[r0+j-1] <= new_A:
                del(a[p]); a[r0+j:r0+j] = [new_A]; continue   
            while sig < 1:
                m = int((l+r0)/2)
                if a[m] > new_A:
                    r0 = m
                elif a[m+1] < new_A:
                    l = m+1
                else:
                    del(a[p]); a[m+1:m+1] = [new_A]                
                    sig = 1

elif revlad > 0:
    l, r, Qu = q[0][0], q[0][1], int((k+5)/5)
    a[l:r+1] = sorted(a[l:r+1])
    for i in range(1, Q):
        l, r, l0, m, sig = q[i][0], q[i][1], q[i-1][0], 0, 0
        if k > r: break
        if r < l0:
            a[l:r+1] = sorted(a[l:r+1]); continue        
        count = list(range(l, l0))
        for j in range(len(count)):
            p, new_A = count[j], a[count[j]]
            if a[l0] >= new_A:
                del(a[p]); a[l0:l0] = [new_A]; continue
            elif a[r] <= new_A:
                del(a[p]); a[r:r] = [new_A]; continue   
            while sig < 1:
                m = int((l0+r)/2)
                if a[m] > new_A:
                    r = m
                elif a[m+1] < new_A:
                    l0 = m+1
                else:
                    del(a[p]); a[m+1:m+1] = [new_A]                
                    sig = 1
    
elif span_q < 1e9 and a != b:
    for i in count:
        l, r = q[i][0], q[i][1]
        a[l:(r+1)] = sorted(a[l:(r+1)])
else:
    a[pmin:qmax+1] = sorted(a[pmin:qmax+1])   
print(a[k])

Problem solution in Java.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
 static Scanner std = new Scanner(System.in);
        
    public static int nI(){
        return std.nextInt();
    }

    public static long nL(){
        return std.nextLong();
    }

    public static String next(){
        return std.next();
    }

    public static String nextL(){
        return std.nextLine();
    }
    
    public static int[] nA(int n){
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = nI();
        }
        return arr;
    }
    
    public static long fact(int n){
        if(n==1) return 1;
        return n*fact(n-1);
    }

    public static void printArray(int[] arr, int n ){
        for(int i=0;i<n;i++) System.out.print(arr[i]+" ");
        System.out.println();
    }

    public static void printArray2(int[][] arr, int n, int m){
        for(int i=0;i<n;i++) for(int j=0;j<m;j++) System.out.print(arr[i][j]+" "); System.out.println();        
    }


    public static void print(String str){
        System.out.print(""+str+" ");
    }

    public static void pln(String str){
        System.out.println(""+str);
    }

    private static int gcd(int number1, int number2) //Finds GCD of 2 numbers.
    {
        if(number2 == 0)
        {
            return number1;
        }
        return gcd(number2, number1%number2);
    }

    public static int dcf(int p, int k){
        int t=0;
        while(t*p<k){
            t++;
        }
        if(t*p==k){
            return t*p;
        }
        else{
            return (t-1)*p;
        }
    }

    public static int pf(int g){
        for(int i=2;i<=(g/2+1);i++){
            if(g%i==0){
                return i;
            }
        }
        return g;
    }

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        int n = nI();
        int q = nI();
        int k = nI();
        int[] arr = nA(n);
        ArrayList<Integer> a1 = new ArrayList<>();
        int[] arr1 = new int[q];
        int[] arr2 = new int[q];
        for(int h=0;h<q;h++){
            arr1[h] = nI();
            arr2[h] = nI();
        }
        int dd = k;
        int ee = k;
        for(int h=q-1;h>=0;h--){
            if(dd<=arr1[h] && ee>=arr2[h]){
                continue;
            }
            if((arr1[h]<=dd && arr2[h]>=dd) || (arr1[h]<=ee && arr2[h]>=ee)){
                if(arr1[h]<dd){
                    dd = arr1[h];
                }
                if(arr2[h]>ee){
                    ee = arr2[h];
                }
                a1.add(h);
            }
        }
        if(dd==0 && ee == n-1){
            Arrays.sort(arr);
        }
        else{
            for(int h=a1.size()-1;h>=0;h--){
                int ff = a1.get(h);
                Arrays.sort(arr, arr1[ff], arr2[ff]+1);
               // printArray(arr,n);
            }
        }
        pln(""+arr[k]);
    }
}

Problem solution in C++.

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

typedef char Val;
struct Sum {
int cnt;
Sum() : cnt(0) {}
Sum(const Val &val, int pos) : cnt(val) {}
Sum &operator+=(const Sum &that) { cnt += that.cnt; return *this; }
Sum operator+(const Sum &that) const { return Sum(*this) += that; }
};
struct Add {
int assign;
Add() : assign(-1) {}
explicit Add(int a) : assign(a) {}
Add &operator+=(const Add &that) {
if(that.assign != -1)
assign = that.assign;
return *this;
}
void addToVal(Val &val, int pos) const {
if(assign != -1)
val = assign != 0;
}
void addToSum(Sum &sum, int left, int right) const {
if(assign != -1)
sum.cnt = assign != 0 ? right - left : 0;
}
};

struct SegmentTree {
vector<Val> leafs;
vector<Sum> nodes;
vector<Add> add;
vector<int> leftpos, rightpos;
int n, n2;
void init(int n_, const Val &v = Val()) { init(vector<Val>(n_, v)); }
void init(const vector<Val> &u) {
n = 1; while(n < (int)u.size()) n *= 2;
n2 = (n - 1) / 2 + 1;
leafs = u; leafs.resize(n, Val());
nodes.resize(n);
for(int i = n - 1; i >= n2; -- i)
nodes[i] = Sum(leafs[i * 2 - n], i * 2 - n) + Sum(leafs[i * 2 + 1 - n], i * 2 + 1 - n);
for(int i = n2 - 1; i > 0; -- i)
nodes[i] = nodes[i * 2] + nodes[i * 2 + 1];
add.assign(n, Add());

leftpos.resize(n); rightpos.resize(n);
for(int i = n - 1; i >= n2; -- i) {
leftpos[i] = i * 2 - n;
rightpos[i] = (i * 2 + 1 - n) + 1;
}
for(int i = n2 - 1; i > 0; -- i) {
leftpos[i] = leftpos[i * 2];
rightpos[i] = rightpos[i * 2 + 1];
}
}
Val get(int i) {
int indices[128];
int k = getIndices(indices, i, i + 1);
propagateRange(indices, k);
return leafs[i];
}
Sum getRangeCommutative(int i, int j) {
int indices[128];
int k = getIndices(indices, i, j);
propagateRange(indices, k);
Sum res = Sum();
for(int l = i + n, r = j + n; l < r; l >>= 1, r >>= 1) {
if(l & 1) res += sum(l ++);
if(r & 1) res += sum(-- r);
}
return res;
}
Sum getRange(int i, int j) {
int indices[128];
int k = getIndices(indices, i, j);
propagateRange(indices, k);
Sum res = Sum();
for(; i && i + (i&-i) <= j; i += i&-i)
res += sum((n + i) / (i&-i));
for(k = 0; i < j; j -= j&-j)
indices[k ++] = (n + j) / (j&-j) - 1;
while(-- k >= 0) res += sum(indices[k]);
return res;
}
void set(int i, const Val &x) {
int indices[128];
int k = getIndices(indices, i, i + 1);
propagateRange(indices, k);
leafs[i] = x;
mergeRange(indices, k);
}
void addToRange(int i, int j, const Add &x) {
if(i >= j) return;
int indices[128];
int k = getIndices(indices, i, j);
propagateRange(indices, k);
int l = i + n, r = j + n;
if(l & 1) { int p = (l ++) - n; x.addToVal(leafs[p], p); }
if(r & 1) { int p = (-- r) - n; x.addToVal(leafs[p], p); }
for(l >>= 1, r >>= 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) add[l ++] += x;
if(r & 1) add[-- r] += x;
}
mergeRange(indices, k);
}
private:
int getIndices(int indices[], int i, int j) const {
int k = 0, l, r;
if(i >= j) return 0;
for(l = (n + i) >> 1, r = (n + j - 1) >> 1; l != r; l >>= 1, r >>= 1) {
indices[k ++] = l;
indices[k ++] = r;
}
for(; l; l >>= 1) indices[k ++] = l;
return k;
}
void propagateRange(int indices[], int k) {
for(int i = k - 1; i >= 0; -- i)
propagate(indices[i]);
}
void mergeRange(int indices[], int k) {
for(int i = 0; i < k; ++ i)
merge(indices[i]);
}
inline void propagate(int i) {
if(i >= n) return;
add[i].addToSum(nodes[i], leftpos[i], rightpos[i]);
if(i * 2 < n) {
add[i * 2] += add[i];
add[i * 2 + 1] += add[i];
} else {
add[i].addToVal(leafs[i * 2 - n], i * 2 - n);
add[i].addToVal(leafs[i * 2 + 1 - n], i * 2 + 1 - n);
}
add[i] = Add();
}
inline void merge(int i) {
if(i >= n) return;
nodes[i] = sum(i * 2) + sum(i * 2 + 1);
}
inline Sum sum(int i) {
propagate(i);
return i < n ? nodes[i] : Sum(leafs[i - n], i - n);
}
};

int main() {
int n; int q; int k;
while(~scanf("%d%d%d", &n, &q, &k)) {
vector<int> A(n);
for(int i = 0; i < n; ++ i)
scanf("%d", &A[i]);
vector<int> l(q), r(q);
for(int i = 0; i < q; ++ i)
scanf("%d%d", &l[i], &r[i]), ++ r[i];
vi values = A;
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
int lo = 0, up = (int)values.size() - 1;
while(up - lo > 0) {
int mid = (lo + up + 1) / 2;
vector<Val> initvals(n);
rep(i, n)
initvals[i] = values[mid] <= A[i];
SegmentTree segt; segt.init(initvals);
rep(i, q) {
int cnt0 = r[i] - l[i] - segt.getRangeCommutative(l[i], r[i]).cnt;
segt.addToRange(l[i], l[i] + cnt0, Add(0));
segt.addToRange(l[i] + cnt0, r[i], Add(1));
}
if(segt.get(k))
lo = mid;
else
up = mid - 1;
}
printf("%dn", values[lo]);
}
return 0;
}

Problem solution in C.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>


struct Query{
    int l, r;
    int ignore;
};

int ar1[75000];
int ar2[75000];

struct Query queries[75000];
struct Query sarea[75000];


int cmp(const void *a, const void *b){
    return (*(int *)a - *(int *)b);
}

void insertionsort(int a[], int N){
    int i, j;
    int v;
    for (i = 1; i < N; i++){
        v = a[i];
        for (j = i; j>0 && a[j - 1] > v; j--){
            a[j] = a[j - 1];
        }
        a[j] = v;
    }
}

int main() {

    int n, q, k1, i, l, r, ign, j,mi,hr,nr,k,changed;
    int si, sj;
    int *a = ar1;
    int *b = ar2;

    scanf("%d %d %d", &n, &q, &k1);
    for (i = 0; i<n; i++){
        scanf("%d", &a[i]);
    }
    for (i = 0; i<q; i++){
        scanf("%d %d", &(queries[i].l), &(queries[i].r));
        queries[i].ignore = 0;
    }
    i = q ;
    do{
        i = i - 1;        
    } while (i >= 0 && (k1 < queries[i].l || k1 > queries[i].r));
    if (i >= 0){
        l = queries[i].l;
        r = queries[i].r;
        ign = i;
        for (i = i-1; i >= 0; i--){
            if (queries[i].r < l || queries[i].l > r){
                queries[i].ignore = 1;
            }
            else{
                if (queries[i].r > r && queries[i].l >= l)
                    r = queries[i].r;
                else if (queries[i].l < l && queries[i].r <= r)
                    l = queries[i].l;
                else  if (queries[i].l < l && queries[i].r > r){
                    ign = i;
                    r = queries[i].r;
                    l = queries[i].l;
                }
            }
        }
        l = 0;
        r = 0;
        si = 0;
        for (i = 0; i <= ign; i++){

            if (!queries[i].ignore){
                for (sj = si - 1; sj >= 0; sj--){
                    if (sarea[sj].l < queries[i].l && queries[i].l < sarea[sj].r) break;
                    if (sarea[sj].l < queries[i].r && queries[i].r < sarea[sj].r) break;
                       if (sarea[sj].l >= queries[i].l && queries[i].r >= sarea[sj].r) break;
                }
                if (sj == -1){
                    qsort(a + queries[i].l, queries[i].r - queries[i].l + 1, sizeof(int), cmp);
                    sarea[si] = queries[i];
                    si++;
                }
                else{
                    changed =0;
                    l = sarea[sj].l;
                    r = sarea[sj].r;
                    if (queries[i].l < l){
                        changed=1;
                        hr = l - queries[i].l;
                        memcpy(b, a + queries[i].l, hr*sizeof(int));
                        //qsort(b, hr, sizeof(int), cmp);
                        insertionsort(b,hr);
                        mi = 0;
                        j = l;
                        k = queries[i].l;
                        nr = (r < queries[i].r ? r : queries[i].r);
                        while (mi < hr && j <= nr)
                        {
                            a[k++] = (b[mi] < a[j] ? b[mi++] : a[j++]);
                        }
                        while (mi < hr) a[k++] = b[mi++];
                        
                    }
                    if (queries[i].r > r){
                        changed+=2;
                        hr = queries[i].r - r;
                        memcpy(b, a + r + 1, hr*sizeof(int));
                        //qsort(b, hr, sizeof(int), cmp);
                        insertionsort(b,hr);
                        mi = hr - 1;
                        j = r;
                        k = queries[i].r;

                        while (mi >= 0 && j >= queries[i].l)
                        {
                            a[k--] = (b[mi] > a[j] ? b[mi--] : a[j--]);
                        }
                        while (mi >= 0) a[k--] = b[mi--];
                        r = queries[i].r;
                    }
                    if (changed){
                        sarea[sj].l = queries[i].l;
                        sarea[sj].r = queries[i].r;
                    }
                }
            }
        }
    }
    printf("%d", a[k1]);
    return 0;
}