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<<"-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);
}
}
}
0 Comments