HackerRank Animal Transport Problem Solution

HackerRank Animal Transport Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Animal Transport Problem Solution.

Capeta is working part-time for an animal shipping company. He needs to pick up animals from various zoos and drop them to other zoos. The company ships four kinds of animals: elephants, dogs, cats, and mice.
There are m zoos, numbered 1 to m. Also, there are n animals. For each animal ¿, Capeta knows its type t, (E for elephant, D for dog, C for cat and M for mouse), source zoo 8; where Capeta has to pick it up from, and destination zoo d; where Capeta needs to deliver it to.

Capeta is given a truck with a huge capacity where n animals can easily fit. He is also given additional instructions:

  1. He must visit the zoos in increasing order. He also cannot skip zoos.
  2. Dogs are scared of elephants, so he is not allowed to bring them together at the same time.
  3. Cats are scared of dogs, so he is not allowed to bring them together at the same time.
  4. Mice are scared of cats, so he is not allowed to bring them together at the same time.
  5. Elephants are scared of mice, so he is not allowed to bring them together at the same
    time.
    Also, loading and unloading animals are complicated, so once an animal is loaded onto the truck, that animal will only be unloaded at its destination.
    Because of these reasons, Capeta might not be able to transport all animals. He will need to ignore some animals. Which ones? The company decided to leave that decision for Capeta. He is asked to prepare a report and present it at a board meeting of the company.
    Capeta needs to report the minimum number of zoos that must be reached so that she is able to transport & animals, for each a from 1 to n.
    Complete the function minimumZooNumbers and return an integer array where the ath integer is the minimum number of zoos that Capeta needs to reach so that she is able to transportæ animals, or -1 if it is impossible to transport & animals.
    He is good at driving, but not so much at planning. Hence, he needs your help.

Input Format
The first line contains a single integer t. the number of test cases.
Each test case consists of four lines. The first line contains two space-separated integers m and n. The second line contains n space-separated characters t1, t2,…, t. The third line contains n space-separated integers $1, $2,…, Sn. The fourth line contains n space- separated integers d1, d2,…, dn.
t, 8, and d, are the details for the ith animal, as described in the problem statement.
Output Format
For each case, print a single line containing n space-separated integers, where the th Integer is the minimum number of zoos that Capeta needs to reach so that she is able to transport æ animals. If it is not possible to transportæ animals at all, then put-1 instead.

Sample Input 0

2
10 3
E D C
4 1 4
7 5 8
10 6
E D C M E D
1 1 1 2 9 7
2 2 2 4 10 10

Sample Output 0

5 8 -1
2 2 4 10 -1 -1

Explanation 0
First Test Case
Capeta can transport one animal by traveling up to zoo number 5. Just drop the dog there. Next, in order to transport 2 animals (elephant and cat), Capeta has to go up to zoo number
8.
Second Test Case

  • 1 Animal: Drop the elephant to zoo 2.
  • 2 Animal: Drop the elephant and cat to zoo 2.
  • 3 Animal: Drop the elephant and cat to zoo 2. Then drop the mouse to zoo 4.
  • 4 Animal: Drop the elephant and cat to zoo 2. Then drop the mouse to zoo 4. Finally, drop either the elephant or the dog to 10.
    It is impossible to transport 5 or 6 animals.
HackerRank Animal Transport Problem Solution
HackerRank Animal Transport Problem Solution

Animal Transport C++ Solution

#include <bits/stdc++.h>

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long

using namespace std;

const int N = (5e4 + 100), mod = (1e9) + 7;

char t[N];
int s[N], d[N], a[N], b[N];

int deoec[4 * N], deodm[4 * N], aec[4 * N], adm[4 * N];

vector<int> ec[N], dm[N];

void build(int (&deo)[4 * N], int (&a)[4 * N], int v, int tl, int tr) {
	if(tl == tr) {
		deo[v] = 0;
		a[v] = 0;
		return;
	}
	int tm = (tl + tr) >> 1;
	build(deo, a, v * 2 + 1, tl, tm);
	build(deo, a, v * 2 + 2, tm + 1, tr);
	a[v] = 0;
	deo[v] = max(deo[v * 2 + 1], deo[v * 2 + 2]) + a[v];
}

void add(int (&deo)[4 * N], int (&a)[4 * N], int l, int r, int val, int v, int tl, int tr) {
	if(tr < l || r < tl) {
		return;
	}
	if(l <= tl && tr <= r) {
		deo[v] += val;
		a[v] += val;
		return;
	}
	int tm = (tl + tr) >> 1;
	add(deo, a, l, r, val, v * 2 + 1, tl, tm);
	add(deo, a, l, r, val, v * 2 + 2, tm + 1, tr);
	deo[v] = max(deo[v * 2 + 1], deo[v * 2 + 2]) + a[v];
}

int get(int (&deo)[4 * N], int (&a)[4 * N], int l, int r, int v, int tl, int tr) {
	if(tr < l || r < tl) {
		return 0;
	}
	if(l <= tl && tr <= r) {
		return deo[v];
	}
	int tm = (tl + tr) >> 1;
	return max(get(deo, a, l, r, v * 2 + 1, tl, tm), get(deo, a, l, r, v * 2 + 2, tm + 1, tr)) + a[v];
}

int main(){

	int te;
	scanf("%d", &te);
	for(; te--; ) {
		int n, m;
		scanf("%d%d", &n, &m);
		for(int i = 0; i < m; i++) {
			scanf(" %c", &t[i]);
		}
		for(int i = 0; i < m; i++) {
			scanf(" %d", &s[i]);
		}
		for(int i = 0; i < m; i++) {
			scanf(" %d", &d[i]);
		}

		for(int i = 0; i <= n; i++) {
			ec[i].clear();
			dm[i].clear();
		}

		for(int i = 0; i < m; i++) {
			if(s[i] > d[i]) continue;
			if(t[i] == 'E' || t[i] == 'C') {
				ec[d[i]].pb(s[i]);
			} else {
				dm[d[i]].pb(s[i]);
			}
		}
		for(int i = 0; i <= n; i++) {
			a[i] = mod;
		}
		for(int i = 0; i <= m; i++) {
			b[i] = mod;
		}
		build(deoec, aec, 0, 0, n);
		build(deodm, adm, 0, 0, n);
		for(int i = 1; i <= n; i++) {
			for(int v : ec[i]) {
				add(deoec, aec, 0, v, 1, 0, 0, n);
			}
			for(int v : dm[i]) {
				add(deodm, adm, 0, v, 1, 0, 0, n);
			}
			a[i] = min(max(get(deoec, aec, 0, i, 0, 0, n), get(deodm, adm, 0, i, 0, 0, n)), mod);
			add(deoec, aec, i, i, a[i], 0, 0, n);
			add(deodm, adm, i, i, a[i], 0, 0, n);
			if(a[i] != mod) b[a[i]] = min(b[a[i]], i);
		}
		for(int i = m - 1; i >= 0; i--) {
			b[i] = min(b[i + 1], b[i]);
		}
		for(int i = 1; i <= m; i++) {
			printf("%d%c", b[i] == mod ? -1 : b[i], " \n"[i == m]);
		}
	}

	return 0;
}

Animal Transport Java Solution


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 E4 {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		for(int T = ni();T > 0;T--){
			int n = ni(), m = ni();
			int[][] ts = new int[m][3];
			for(int i = 0;i < m;i++){
				ts[i][0] = "EC".indexOf(nc()) >= 0 ? 0 : 1;
			}
			for(int i = 0;i < m;i++){
				ts[i][1] = ni()*2;
			}
			for(int i = 0;i < m;i++){
				ts[i][2] = ni()*2-1;
			}
			Arrays.sort(ts, new Comparator<int[]>() {
				public int compare(int[] a, int[] b) {
					if(a[2] != b[2])return a[2] - b[2];
					return a[1] - b[1];
				}
			});
			
			StarrySkyTree sst0 = new StarrySkyTree(2*n+3);
			StarrySkyTree sst1 = new StarrySkyTree(2*n+3);
			int[] reach = new int[m+2];
			Arrays.fill(reach, -1);
			
			int p = 0;
			for(int i = 1;i <= 2*n;i++){
				while(p < m && ts[p][2] <= i){
					if(ts[p][1] < ts[p][2]){
						if(ts[p][0] == 0){
							sst0.add(0, ts[p][1], -1);
						}else{
							sst1.add(0, ts[p][1], -1);
						}
					}
					p++;
				}
				int mat = 0;
				{
					int max = -sst1.min(0, i);
					sst0.add(i, i+1, -max);
					mat = Math.max(mat, max);
				}
				{
					int max = -sst0.min(0, i);
					sst1.add(i, i+1, -max);
					mat = Math.max(mat, max);
				}
				if(reach[mat] == -1)reach[mat] = (i+1)/2;
			}
			
			
			for(int i = m;i >= 1;i--){
				if(reach[i] != -1)continue;
				reach[i] = reach[i+1];
			}
			for(int i = 1;i <= m;i++){
				out.print(reach[i] + " ");
			}
			out.println();
		}
	}
	
	public static int upperBound(int[] a, int v){ return upperBound(a, 0, a.length, v); }
	public static int upperBound(int[] a, int l, int r, int v)
	{
		int low = l-1, high = r;
		while(high-low > 1){
			int h = high+low>>>1;
			if(a[h] <= v){
				low = h;
			}else{
				high = h;
			}
		}
		return low;
	}

	
	public static class StarrySkyTree {
		public int M, H, N;
		public int[] st;
		public int[] plus;
		public int I = Integer.MAX_VALUE/4; // I+plus<int
		
		public StarrySkyTree(int n)
		{
			N = n;
			M = Integer.highestOneBit(Math.max(n-1, 1))<<2;
			H = M>>>1;
			st = new int[M];
			plus = new int[H];
		}
		
		public StarrySkyTree(int[] a)
		{
			N = a.length;
			M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
			H = M>>>1;
			st = new int[M];
			for(int i = 0;i < N;i++){
				st[H+i] = a[i];
			}
			plus = new int[H];
			Arrays.fill(st, H+N, M, I);
			for(int i = H-1;i >= 1;i--)propagate(i);
		}
		
		private void propagate(int i)
		{
			st[i] = Math.min(st[2*i], st[2*i+1]) + plus[i];
		}
		
		public void add(int l, int r, int v){ if(l < r)add(l, r, v, 0, H, 1); }
		
		private void add(int l, int r, int v, int cl, int cr, int cur)
		{
			if(l <= cl && cr <= r){
				if(cur >= H){
					st[cur] += v;
				}else{
					plus[cur] += v;
					propagate(cur);
				}
			}else{
				int mid = cl+cr>>>1;
				if(cl < r && l < mid){
					add(l, r, v, cl, mid, 2*cur);
				}
				if(mid < r && l < cr){
					add(l, r, v, mid, cr, 2*cur+1);
				}
				propagate(cur);
			}
		}
		
		public int min(int l, int r){ return l >= r ? I : min(l, r, 0, H, 1);}
		
		private int min(int l, int r, int cl, int cr, int cur)
		{
			if(l <= cl && cr <= r){
				return st[cur];
			}else{
				int mid = cl+cr>>>1;
				int ret = I;
				if(cl < r && l < mid){
					ret = Math.min(ret, min(l, r, cl, mid, 2*cur));
				}
				if(mid < r && l < cr){
					ret = Math.min(ret, min(l, r, mid, cr, 2*cur+1));
				}
				return ret + plus[cur];
			}
		}
		
		public void fall(int i)
		{
			if(i < H){
				if(2*i < H){
					plus[2*i] += plus[i];
					plus[2*i+1] += plus[i];
				}
				st[2*i] += plus[i];
				st[2*i+1] += plus[i];
				plus[i] = 0;
			}
		}
		
		public int firstle(int l, int v) {
			int cur = H+l;
			for(int i = 1, j = Integer.numberOfTrailingZeros(H)-1;i <= cur;j--){
				fall(i);
				i = i*2|cur>>>j&1;
			}
			while(true){
				fall(cur);
				if(st[cur] <= v){
					if(cur < H){
						cur = 2*cur;
					}else{
						return cur-H;
					}
				}else{
					cur++;
					if((cur&cur-1) == 0)return -1;
					cur = cur>>>Integer.numberOfTrailingZeros(cur);
				}
			}
		}
		
		public int lastle(int l, int v) {
			int cur = H+l;
			for(int i = 1, j = Integer.numberOfTrailingZeros(H)-1;i <= cur;j--){
				fall(i);
				i = i*2|cur>>>j&1;
			}
			while(true){
				fall(cur);
				if(st[cur] <= v){
					if(cur < H){
						cur = 2*cur+1;
					}else{
						return cur-H;
					}
				}else{
					if((cur&cur-1) == 0)return -1;
					cur = cur>>>Integer.numberOfTrailingZeros(cur);
					cur--;
				}
			}
		}
		
		public int[] toArray() { return toArray(1, 0, H, new int[H]); }
		
		private int[] toArray(int cur, int l, int r, int[] ret)
		{
			if(r-l == 1){
				ret[cur-H] = st[cur];
			}else{
				toArray(2*cur, l, l+r>>>1, ret);
				toArray(2*cur+1, l+r>>>1, r, ret);
				for(int i = l;i < r;i++)ret[i] += plus[cur];
			}
			return ret;
		}
	}


	
	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 E4().run(); }
	
	private byte[] inbuf = new byte[1024];
	public 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))){ // when nextLine, (isSpaceChar(b) && 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)); }
}

Animal Transport D Solution

/+ dub.sdl:
    name "A"
    dependency "dcomp" version=">=0.9.0"
+/

import std.stdio, std.algorithm, std.range, std.conv;
// import dcomp.foundation, dcomp.scanner;

// import dcomp.array;
// import dcomp.segtree.lazyseg;

void solve() {
    int m, n;
    sc.read(m, n);

    int[][][2] g;
    g[0] = new int[][](m+1);
    g[1] = new int[][](m+1);

    {
        int[] ty = new int[n];
        foreach (i; 0..n) {
            char c;
            sc.read(c);
            if (c == 'E' || c == 'C') ty[i] = 0;
            else ty[i] = 1;
        }
        int[] s, t;
        sc.read(s, t);

        foreach (i; 0..n) {
            g[ty[i]][t[i]] ~= s[i];
        }
    }

    alias Seg = LazySeg!(
        int, int,
        (a, b) => max(a, b),
        "a+b",
        "a+b",
        -(10^^9), 0
    );

    Seg[2] seg;
    seg[0] = Seg(m+1); seg[0][0] = 0;
    seg[1] = Seg(m+1); seg[1][0] = 0;
    int ba = 0;
    int[] res = new int[](n); res[] = -1;
    foreach (r; 1..m+1) {
//        writeln("start ", r);
        foreach (ty; 0..2) {
            g[ty][r].sort!"a>b";
            foreach (li; g[ty][r].group) {
                int l = li[0];
                int c = li[1];
                if (r < l) continue;
//                writeln("think ", ty, " ", l, " ", r);
//                writeln("nx ", seg[ty][0..l].sum());
                seg[ty][l] = seg[ty][0..l+1].sum() + c;
            }
            foreach (li; g[ty][r].group) {
                int l = li[0];
                int c = li[1];
                if (r < l) continue;
//                writeln("think ", ty, " ", l, " ", r);
                seg[ty][0..l] += c;
            }
        }
        int w = max(seg[0][0..r].sum(), seg[1][0..r].sum());
        seg[0][r] = w; seg[1][r] = w;
//        writeln(iota(m+1).map!(i => seg[0][i..i+1].sum));
//        writeln(iota(m+1).map!(i => seg[1][i..i+1].sum));        
        if (ba < w) {
            res[ba..w] = r;
            ba = w;
        }
    }
    writeln(res.map!(to!string).join(" "));
}

int main() {
    int t;
    sc.read(t);
    foreach (i; 0..t) solve();
    return 0;
}

Scanner sc;
static this() { sc = new Scanner(stdin); }
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/array.d */
// module dcomp.array;

 
T[N] fixed(T, size_t N)(T[N] a) {return a;}

 
 

 
int[2] findFirst2D(T, U)(in T mp, in U c) {
    import std.conv : to;
    int R = mp.length.to!int;
    int C = mp[0].length.to!int;
    foreach (i; 0..R) {
        foreach (j; 0..C) {
            if (mp[i][j] == c) return [i, j];
        }
    }
    assert(false);
}

 
 

 
auto ref at2D(T, U)(ref T mp, in U idx) {
    return mp[idx[0]][idx[1]];
}

 
 
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;

// import dcomp.container.stackpayload;

 
class Scanner {
    import std.stdio : File;
    import std.conv : to;
    import std.range : front, popFront, array, ElementType;
    import std.array : split;
    import std.traits : isSomeChar, isStaticArray, isArray; 
    import std.algorithm : map;
    File f;
    this(File f) {
        this.f = f;
    }
    char[512] lineBuf;
    char[] line;
    private bool succW() {
        import std.range.primitives : empty, front, popFront;
        import std.ascii : isWhite;
        while (!line.empty && line.front.isWhite) {
            line.popFront;
        }
        return !line.empty;
    }
    private bool succ() {
        import std.range.primitives : empty, front, popFront;
        import std.ascii : isWhite;
        while (true) {
            while (!line.empty && line.front.isWhite) {
                line.popFront;
            }
            if (!line.empty) break;
            line = lineBuf[];
            f.readln(line);
            if (!line.length) return false;
        }
        return true;
    }

    private bool readSingle(T)(ref T x) {
        import std.algorithm : findSplitBefore;
        import std.string : strip;
        import std.conv : parse;
        if (!succ()) return false;
        static if (isArray!T) {
            alias E = ElementType!T;
            static if (isSomeChar!E) {
                 
                 
                auto r = line.findSplitBefore(" ");
                x = r[0].strip.dup;
                line = r[1];
            } else static if (isStaticArray!T) {
                foreach (i; 0..T.length) {
                    bool f = succW();
                    assert(f);
                    x[i] = line.parse!E;
                }
            } else {
                StackPayload!E buf;
                while (succW()) {
                    buf ~= line.parse!E;
                }
                x = buf.data;
            }
        } else {
            x = line.parse!T;
        }
        return true;
    }
    int read(T, Args...)(ref T x, auto ref Args args) {
        if (!readSingle(x)) return 0;
        static if (args.length == 0) {
            return 1;
        } else {
            return 1 + read(args);
        }
    }
}


 
 

 
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/segtree/primitive.d */
// module dcomp.segtree.primitive;

import std.conv : to;

struct SegTree(alias E, Args...) {
    import std.traits : ReturnType;
    alias Engine = E!Args;
    alias T = Engine.DataType;
    alias L = Engine.LazyType;

    Engine eng;

    this(size_t n) { eng = Engine(n.to!uint); }
    this(T[] first) { eng = Engine(first); }

    @property size_t length() const { return eng.length(); }
    @property size_t opDollar() const { return eng.length(); }
    
    struct Range {
        Engine* eng;
        size_t start, end;
        @property const(T) sum() {
            return eng.sum(start.to!uint, end.to!uint);
        }
    }
    const(T) opIndex(size_t k) {
        assert(0 <= k && k < eng.length());
        return eng.single(k.to!uint);
    }
    void opIndexAssign(T x, size_t k) {
        assert(0 <= k && k < eng.length());
        eng.singleSet(k.to!uint, x);
    }
    size_t[2] opSlice(size_t dim : 0)(size_t start, size_t end) {
        assert(0 <= start && start <= end && end <= eng.length());
        return [start, end];
    }
    Range opIndex(size_t[2] rng) {
        return Range(&eng, rng[0].to!uint, rng[1].to!uint);
    }
    static if (!is(L == void)) {
        void opIndexOpAssign(string op : "+")(L x, size_t[2] rng) {
            eng.add(rng[0].to!uint, rng[1].to!uint, x);
        }
    }
}

import std.traits : isInstanceOf;

ptrdiff_t binSearchLeft(alias pred, TR)(TR t, ptrdiff_t a, ptrdiff_t b) 
if (isInstanceOf!(SegTree, TR)) {
    return TR.Engine.BinSearch!(false, pred)(t.eng, a.to!int, b.to!int);
}

ptrdiff_t binSearchRight(alias pred, TR)(TR t, ptrdiff_t a, ptrdiff_t b) 
if (isInstanceOf!(SegTree, TR)) {
    return TR.Engine.BinSearch!(true, pred)(t.eng, a.to!int, b.to!int);
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/foundation.d */
 
// module dcomp.foundation;

 
static if (__VERSION__ <= 2070) {
    /*
    Copied by https://github.com/dlang/phobos/blob/master/std/algorithm/iteration.d
    Copyright: Andrei Alexandrescu 2008-.
    License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
    */
    template fold(fun...) if (fun.length >= 1) {
        auto fold(R, S...)(R r, S seed) {
            import std.algorithm : reduce;
            static if (S.length < 2) {
                return reduce!fun(seed, r);
            } else {
                import std.typecons : tuple;
                return reduce!fun(tuple(seed), r);
            }
        }
    }
     
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/container/stackpayload.d */
// module dcomp.container.stackpayload;

 
struct StackPayload(T, size_t MINCAP = 4) if (MINCAP >= 1) {
    import core.exception : RangeError;

    private T* _data;
    private uint len, cap;

    @property bool empty() const { return len == 0; }
    @property size_t length() const { return len; }
    alias opDollar = length;

     
    inout(T)[] data() inout { return (_data) ? _data[0..len] : null; }
    
    ref inout(T) opIndex(size_t i) inout {
        version(assert) if (len <= i) throw new RangeError();
        return _data[i];
    }  
    ref inout(T) front() inout { return this[0]; }  
    ref inout(T) back() inout { return this[$-1]; }  

    void reserve(size_t newCap) {
        import core.memory : GC;
        import core.stdc.string : memcpy;
        import std.conv : to;
        if (newCap <= cap) return;
        void* newData = GC.malloc(newCap * T.sizeof);
        cap = newCap.to!uint;
        if (len) memcpy(newData, _data, len * T.sizeof);
        _data = cast(T*)(newData);
    }  
    void free() {
        import core.memory : GC;
        GC.free(_data);
    }  
     
    void clear() {
        len = 0;
    }

    void insertBack(T item) {
        import std.algorithm : max;
        if (len == cap) reserve(max(cap * 2, MINCAP));
        _data[len++] = item;
    }  
    alias opOpAssign(string op : "~") = insertBack;  
    void removeBack() {
        assert(!empty, "StackPayload.removeBack: Stack is empty");
        len--;
    }  
}

 
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/segtree/lazyseg.d */
// module dcomp.segtree.lazyseg;

// import dcomp.segtree.primitive;

import std.functional : binaryFun;

 
alias LazySeg(T, L, alias opTT, alias opTL, alias opLL, T eT, L eL, alias Engine = LazySegEngine) =
    SegTree!(Engine, T, L , binaryFun!opTT, binaryFun!opTL, binaryFun!opLL, eT, eL);

 
 


struct LazySegEngine(T, L, alias opTT, alias opTL, alias opLL, T eT, L eL) {
    import std.typecons : Tuple;
    alias DataType = T;
    alias LazyType = L;
    alias BinSearch = binSearchLazy;
    alias S = Tuple!(T, "d", L, "lz");
    uint n, sz, lg;
    S[] s;
    this(uint n) {
        import std.conv : to;
        import std.algorithm : each;
        this.n = n;
        uint lg = 0;
        while ((2^^lg) < n) lg++;
        this.lg = lg;
        sz = 2^^lg;
        s = new S[](2*sz);
        s.each!((ref x) => x = S(eT, eL));
    }
    this(T[] first) {
        import std.conv : to;
        import std.algorithm : each;
        n = first.length.to!uint;
        uint lg = 0;
        while ((2^^lg) < n) lg++;
        this.lg = lg;
        sz = 2^^lg;

        s = new S[](2*sz);
        s.each!((ref x) => x = S(eT, eL));
        foreach (i; 0..n) {
            s[sz+i].d = first[i];
        }
        foreach_reverse (i; 1..sz) {
            update(i);
        }
    }
    @property uint length() const { return n; }
    pragma(inline):
    private void lzAdd(uint k, in L x) {
        s[k].lz = opLL(s[k].lz, x);
        s[k].d = opTL(s[k].d, x);
    }
    public void push(uint k) {
        if (s[k].lz == eL) return;
        lzAdd(2*k, s[k].lz);
        lzAdd(2*k+1, s[k].lz);
        s[k].lz = eL;
    }
    private void update(uint k) {
        s[k].d = opTT(s[2*k].d, s[2*k+1].d);
    }
    T single(uint k) {
        k += sz;
        foreach_reverse (uint i; 1..lg+1) {
            push(k>>i);
        }
        return s[k].d;
    }
    void singleSet(uint k, T x) {
        k += sz;
        foreach_reverse (uint i; 1..lg+1) {
            push(k>>i);
        }
        s[k].d = x;
        foreach (uint i; 1..lg+1) {
            update(k>>i);
        }
    }
    T sum(uint a, uint b) {
        assert(0 <= a && a <= b && b <= n);
        if (a == b) return eT;
        a += sz; b--; b += sz;
        uint tlg = lg;
        while (true) {
            uint k = a >> tlg;
            if (a >> tlg != b >> tlg) {
                tlg++;
                break;
            }
            if (((a-1) >> tlg) + 2 == (b+1) >> tlg) return s[k].d;
            push(k);
            tlg--;
        }
        T sm = eT;
        foreach_reverse (l; 0..tlg) {
            uint k = a >> l;
            if ((a-1)>>l != a>>l) {
                sm = opTT(s[k].d, sm);
                break;
            }
            push(k);
            if (!((a >> (l-1)) & 1)) sm = opTT(s[2*k+1].d, sm);
        }
        foreach_reverse (l; 0..tlg) {
            uint k = b >> l;
            if (b>>l != (b+1)>>l) {
                sm = opTT(sm, s[k].d);
                break;
            }
            push(k);
            if ((b >> (l-1)) & 1) sm = opTT(sm, s[2*k].d);
        }
        return sm;
    }
    void add(uint a, uint b, L x) {
        assert(0 <= a && a <= b && b <= n);
        if (a == b) return;
        a += sz; b--; b += sz;
        uint tlg = lg;
        while (true) {
            uint k = a >> tlg;
            if (a >> tlg != b >> tlg) {
                tlg++;
                break;
            }
            if (((a-1) >> tlg) + 2 == (b+1) >> tlg) {
                lzAdd(k, x);
                foreach (l; tlg+1..lg+1) {
                    update(a >> l);
                }
                return;
            }
            push(k);
            tlg--;
        }
        foreach_reverse (l; 0..tlg) {
            uint k = a >> l;
            if ((a-1)>>l != a>>l) {
                lzAdd(k, x);
                foreach (h; l+1..tlg) {
                    update(a >> h);
                }
                break;
            }
            push(k);
            if (!((a >> (l-1)) & 1)) lzAdd(2*k+1, x);
        }
        foreach_reverse (l; 0..tlg) {
            uint k = b >> l;
            if (b>>l != (b+1)>>l) {
                lzAdd(k, x);
                foreach (h; l+1..tlg) {
                    update(b >> h);
                }
                break;
            }
            push(k);
            if ((b >> (l-1)) & 1) lzAdd(2*k, x);
        }
        foreach (l; tlg..lg+1) {
            update(a >> l);
        }
    }
}



 


int binSearchLazy(bool rev, alias pred, TR)(TR t, int a, int b) {
    import std.traits : TemplateArgsOf;
    alias args = TemplateArgsOf!TR;
    alias opTT = args[2];
    auto x = args[5];
    with (t) {
        static if (!rev) {
             
            if (pred(x)) return a-1;
            int pos = a;
            void f(int a, int b, int l, int r, int k) {
                if (b <= l || r <= a) return;
                if (a <= l && r <= b && !pred(opTT(x, s[k].d))) {
                    x = opTT(x, s[k].d);
                    pos = r;
                    return;
                }
                if (l+1 == r) return;
                push(k);
                int md = (l+r)/2;
                f(a, b, l, md, 2*k);
                if (pos >= md) f(a, b, md, r, 2*k+1);
            }
            f(a, b, 0, sz, 1);
            return pos;
        } else {
             
            if (pred(x)) return b;
            int pos = b-1;
            void f(int a, int b, int l, int r, int k) {
                if (b <= l || r <= a) return;
                if (a <= l && r <= b && !pred(opTT(x, s[k].d))) {
                    x = opTT(s[k].d, x);
                    pos = l-1;
                    return;
                }
                if (l+1 == r) return;
                push(k);
                int md = (l+r)/2;
                f(a, b, md, r, 2*k+1);
                if (pos < md) f(a, b, l, md, 2*k);
            }
            f(a, b, 0, sz, 1);
            return pos;            
        }
    }
}

/*
This source code generated by dcomp and include dcomp's source code.
dcomp's Copyright: Copyright (c) 2016- Kohei Morita. (https://github.com/yosupo06/dcomp)
dcomp's License: MIT License(https://github.com/yosupo06/dcomp/blob/master/LICENSE.txt)
*/

Animal Transport Pascal Solution

(* Enter your code here. Read input from STDIN. Print output to STDOUT *){$mode objfpc}
uses math;

var
  t,n,m:integer;
  a,b,k,f,res:array[0..100000] of integer;
  it,lazy:array[1..2,0..400000] of integer;

procedure sort(l,r: longint);
      var
         i,j,x,y: longint;
      begin
         i:=l;
         j:=r;
         x:=b[random(r-l+1)+l];
         repeat
           while b[i]<x do inc(i);
           while x<b[j] do dec(j);
           if not(i>j) then
             begin
                y:=a[i]; a[i]:=a[j]; a[j]:=y;
                y:=b[i]; b[i]:=b[j]; b[j]:=y;
                y:=k[i]; k[i]:=k[j]; k[j]:=y;
                inc(i); dec(j);
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

procedure down(k,xo:integer);
  begin
    it[k,xo*2]:=it[k,xo*2] + lazy[k,xo];
    lazy[k,xo*2]:=lazy[k,xo*2] + lazy[k,xo];
    it[k,xo*2+1]:=it[k,xo*2+1] + lazy[k,xo];
    lazy[k,xo*2+1]:=lazy[k,xo*2+1] + lazy[k,xo];
    lazy[k,xo]:=0;
  end;

procedure increase(k,u,v,i,j,xo:integer);
var mid:integer;
  begin
    if (v < i) or (u > j) then exit;
    if (u <= i) and (j <= v) then
      begin
        inc(it[k,xo]);
        inc(lazy[k,xo]);
        exit;
      end;
    mid:=(i+j) div 2;
    down(k,xo);
    increase(k,u,v,i,mid,xo*2);
    increase(k,u,v,mid+1,j,xo*2+1);
    it[k,xo]:=max(it[k,xo*2] , it[k,xo*2+1]);
  end;

function query(u,v,i,j,xo:integer):integer;
var mid:integer;
  begin
    if (v < i) or (u > j) then exit(0);
    if (u <= i) and (j <= v) then exit(max(it[1,xo] , it[2,xo]));
    mid:=(i+j) div 2;
    down(1,xo);
    down(2,xo);
    result:=max(query(u,v,i,mid,xo*2) , query(u,v,mid+1,j,xo*2+1));
    it[1,xo]:=max(it[1,xo*2] , it[1,xo*2+1]);
    it[2,xo]:=max(it[2,xo*2] , it[2,xo*2+1]);
  end;

procedure update(o,w,i,j,xo:integer);
var mid:integer;
  begin
    if i = j then
      begin
        it[1,xo]:=w;
        it[2,xo]:=w;
        exit;
      end;
    mid:=(i+j) div 2;
    down(1,xo);
    down(2,xo);
    if o <= mid then update(o,w,i,mid,xo*2)
    else update(o,w,mid+1,j,xo*2+1);
    it[1,xo]:=max(it[1,xo*2] , it[1,xo*2+1]);
    it[2,xo]:=max(it[2,xo*2] , it[2,xo*2+1]);
  end;

procedure solve;
var i,j:integer; o:char;
  begin
    fillchar(it,sizeof(it),0);
    fillchar(lazy,sizeof(lazy),0);
    readln(m,n);
    for i:=1 to n do res[i]:=m+1;
    for i:=1 to n do
      begin
        read(o);
        if (o = 'E') or (o = 'C') then k[i]:=1
        else k[i]:=2;
        if i < n then read(o);
      end;
    readln;
    for i:=1 to n do read(a[i]);
    for i:=1 to n do read(b[i]);
    sort(1,n);
    //for i:=1 to n do writeln(k[i],' ',a[i],' ',b[i]);
    j:=1;
    for i:=1 to m do
      begin
        while (j <= n) and (b[j] <= i) do
          begin
            if a[j] <= b[j] then increase(k[j],1,a[j],1,m,1);
            inc(j);
          end;
        f[i]:=query(1,i,1,m,1);
        ///if i = 5 then writeln(f[i],' ',it[2,1]);
        res[f[i]]:=min(res[f[i]] , i);
        update(i,f[i],1,m,1);
      end;
    for i:=n-1 downto 1 do res[i]:=min(res[i] , res[i+1]);
    for i:=1 to n do
      if res[i] = m+1 then write('-1 ') else write(res[i],' ');
    writeln;
  end;

begin           {
  assign(input,'a.inp');
  reset(input);}
  read(t);
  while t > 0 do
    begin
      dec(t);
      solve;
    end;
end.
C++ D HackerRank Solutions java Pascal