# 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 intll 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<<"-1\n";            }            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);        }    }}`