HackerEarth Clothes Arrangement problem solution

In this HackerEarth Clothes Arrangement problem solution, There is an arrangement of clothes in the form of a stack. There are N clothes with you and each cloth has a color Col[i] associated with it.1st cloth is at the bottom and Nth cloth at the top.

Now you have to answer Q queries:

Each query can be of 2 types:

Type-1 query indicated that you place a cloth of color C on top of the stack.

Type 2 query gives you a color C a number K which means you need to pick the Kth cloth from top having color C.If its not possible print -1.If you find the Kth cloth then you take that cloth out of the stack and put all other clothes back in their original order.For type 2 query if you get a cloth then print the number of clothes you had to pop from the stack before you see your desired cloth.

HackerEarth Clothes Arrangement problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll n,q,col[500005],id,cc,seg[4000006],bit[1000002],pos[500005],ty,idx;
map<ll,ll>mp;
struct qry
{
    ll ty,col,idx;
};
vector<ll>colpos[1000002];
vector<ll>colqry[1000002];
queue<ll>qpo[1000002];
vector<qry>query;
void upd_bit(ll idx,ll val)
{
    while(idx<1000001)
    {
        bit[idx]+=val;
        idx+=(idx&(-idx));
    }
}
ll get_val(ll idx)
{
    ll sm=0;
    while(idx>0)
    {
        sm+=bit[idx];
        idx-=(idx&(-idx));
    }
    return sm;
}
void upd_seg(ll node,ll st,ll en,ll idx,ll val)
{
    if(st==en)
    {
        seg[node]=val;
        return;
    }
    else
    {
        ll mid=(st+en)/2;
        if(idx<=mid)
        upd_seg(2*node,st,mid,idx,val);
        else
        upd_seg(2*node+1,mid+1,en,idx,val);
        seg[node]=seg[2*node]+seg[2*node+1];
    }
}
ll qry(ll node,ll st,ll en,ll k)
{
    if(seg[node]<k||k<=0)
    return -1;
    if(st==en)
    return st;
    else
    {
        ll mid=(st+en)/2;
        if(seg[2*node]>=k)
        return qry(2*node,st,mid,k);
        else
        return qry(2*node+1,mid+1,en,k-seg[2*node]);
    }
}
int main()
{
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    freopen("samp.txt","r",stdin);
    freopen("sout.txt","w",stdout);
    ll i,j,k;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>col[i];
        mp[col[i]];
    }
    cin>>q;
    for(i=1;i<=q;i++)
    {
        cin>>ty;
        if(ty==1)
        {
            cin>>cc;
            mp[cc];
            query.push_back({1,cc,-1});
        }
        else
        {
            cin>>cc>>idx;
            mp[cc];
            query.push_back({2,cc,idx});
        }
    }
    j=1;
    for(auto it:mp)
    {
        mp[it.first]=j;
        j++;
    }
    ll noc=j-1;
    for(i=1;i<=n;i++)
    {
        col[i]=mp[col[i]];
        colpos[col[i]].push_back(i);
    }
    ll cur=n+1;
    for(i=0;i<query.size();i++)
    {
        query[i].col=mp[query[i].col];
        if(query[i].ty==1)
        {
            qpo[query[i].col].push(cur);
            colqry[query[i].col].push_back(i);
            cur++;
        }
        else
        {
            colqry[query[i].col].push_back(i);
        }
    }
    for(i=1;i<=noc;i++)
    {
        for(j=0;j<colpos[i].size();j++)
        {
            ll np=colpos[i][j];
            upd_seg(1,1,cur,np,1);
        }
        ll jj=colqry[i].size();
        ll cidx;
        vector<ll>vks;
        for(j=0;j<jj;j++)
        {
            ll qnum=colqry[i][j];
            if(query[qnum].ty==1)
            {
                cidx=qpo[i].front();
                qpo[i].pop();
                vks.push_back(cidx);
                upd_seg(1,1,cur,cidx,1);
            }
            else
            {
                cidx=query[qnum].idx;
                ll tot=seg[1]+1-cidx;
                ll gp=qry(1,1,cur,tot);
                pos[qnum]=gp;
                if(gp>=1)
                upd_seg(1,1,cur,gp,0);
            }
        }
        for(j=0;j<colpos[i].size();j++)
        {
            ll np=colpos[i][j];
            upd_seg(1,1,cur,np,0);
        }
        for(auto it:vks)
        {
            upd_seg(1,1,cur,it,0);
        }
    }
    ll avl=n;
    for(i=0;i<query.size();i++)
    {
        if(query[i].ty==1)
        {
            avl++;
        }
        else
        {
            if(pos[i]==-1)
            {
                cout<<"-1n";
            }
            else
            {
                ll gt=get_val(1e6)-get_val(pos[i]);
                cout<<avl-pos[i]-gt<<"n";
                upd_bit(pos[i],1);
            }
        }
    }
    return 0;
}

Second solution

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.OutputStream;
import java.io.IOException;
import java.util.InputMismatchException;
import java.io.InputStreamReader;
import java.io.Writer;
import java.io.BufferedReader;
import java.io.InputStream;


public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        FastPrinter out = new FastPrinter(outputStream);
        ClothesArrangement solver = new ClothesArrangement();
        solver.solve(1, in, out);
        out.close();
    }

    static class ClothesArrangement {
        public void solve(int testNumber, FastScanner in, FastPrinter out) {
            int n = in.nextInt();
            if (n < 1 || n > 500000) throw new AssertionError();
            int[] a = in.readIntArray(n);
            int q = in.nextInt();
            if (q < 1 || q > 500000) throw new AssertionError();
            int[] type = new int[q];
            int[] colorQ = new int[q];
            int[] kQ = new int[q];
            final int MAXN = 1000001;
            int[] count = new int[MAXN];
            for (int i : a) count[i]++;
            for (int i : a) if (i < 1 || i > 500000) throw new AssertionError();
            for (int i = 0; i < q; i++) {
                type[i] = in.nextInt();
                if (type[i] != 1 && type[i] != 2) throw new AssertionError();
                colorQ[i] = in.nextInt();
                if (colorQ[i] < 1 || colorQ[i] > 500000) throw new AssertionError();
                if (type[i] == 2) {
                    kQ[i] = in.nextInt();
                    if (kQ[i] < 1 || kQ[i] > 1000000) throw new AssertionError();
                } else {
                    count[colorQ[i]]++;
                }
            }
            int[][] numbers = new int[MAXN][];
            FenwickKth[] f = new FenwickKth[MAXN];
            Fenwick globalF = new Fenwick(n + q);
            for (int i = 0; i < MAXN; i++) {
                if (count[i] > 0) {
                    numbers[i] = new int[count[i]];
                    f[i] = new FenwickKth(count[i]);
                    count[i] = 0;
                }
            }
            int pos = 0;
            for (int x : a) {
                numbers[x][count[x]] = pos;
                f[x].add(count[x], 1);
                globalF.add(pos, 1);
                pos++;
                count[x]++;
            }
            for (int curQ = 0; curQ < q; curQ++) {
                int x = colorQ[curQ];
                if (type[curQ] == 1) {
                    numbers[x][count[x]] = pos;
                    globalF.add(pos, 1);
                    f[x].add(count[x], 1);
                    count[x]++;
                    pos++;
                } else {
                    int k = kQ[curQ];
                    int have = f[x] == null ? 0 : f[x].getSum(Integer.MAX_VALUE);
                    if (have < k) {
                        out.println(-1);
                    } else {
                        int localPos = f[x].getKth(have - k + 1);
                        f[x].add(localPos, -1);
                        int globalPos = numbers[x][localPos];
                        globalF.add(globalPos, -1);
                        out.println(globalF.getSum(globalPos, Integer.MAX_VALUE));
                    }
                }
            }
        }

    }

    static class FastScanner extends BufferedReader {
        public FastScanner(InputStream is) {
            super(new InputStreamReader(is));
        }

        public int read() {
            try {
                int ret = super.read();
                return ret;
            } catch (IOException e) {
                throw new InputMismatchException();
            }
        }

        static boolean isWhiteSpace(int c) {
            return c >= 0 && c <= 32;
        }

        public int nextInt() {
            int c = read();
            while (isWhiteSpace(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int ret = 0;
            while (c >= 0 && !isWhiteSpace(c)) {
                if (c < '0' || c > '9') {
                    throw new NumberFormatException("digit expected " + (char) c
                            + " found");
                }
                ret = ret * 10 + c - '0';
                c = read();
            }
            return ret * sgn;
        }

        public String readLine() {
            try {
                return super.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        public int[] readIntArray(int n) {
            int[] ret = new int[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextInt();
            }
            return ret;
        }

    }

    static class FastPrinter extends PrintWriter {
        public FastPrinter(OutputStream out) {
            super(out);
        }

        public FastPrinter(Writer out) {
            super(out);
        }

    }

    static class FenwickKth {
        int[] a;

        public FenwickKth(int n) {
            a = new int[Integer.highestOneBit(n) << 1];
        }

        public void add(int x, int y) {
            for (int i = x; i < a.length; i |= i + 1) {
                a[i] += y;
            }
        }

        public int getSum(int x) {
            if (x >= a.length) x = a.length - 1;
            int ret = 0;
            for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
                ret += a[i];
            }
            return ret;
        }

        public int getKth(int k) {
            int l = 0;
            int r = a.length;
            while (l < r - 1) {
                int mid = l + r >> 1;
                if (a[mid - 1] >= k) {
                    r = mid;
                } else {
                    k -= a[mid - 1];
                    l = mid;
                }
            }
            return l;
        }

    }

    static class Fenwick {
        int[] a;

        public Fenwick(int n) {
            a = new int[n];
        }

        public void add(int x, int y) {
            for (int i = x; i < a.length; i |= i + 1) {
                a[i] += y;
            }
        }

        public int getSum(int x) {
            if (x >= a.length) x = a.length - 1;
            int ret = 0;
            for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
                ret += a[i];
            }
            return ret;
        }

        public int getSum(int l, int r) {
            return getSum(r - 1) - getSum(l - 1);
        }

    }
}

coding problems solutions