Animal Transport

                            Solution in C :

In C++ :




#include"bits/stdc++.h"
#define F(i,j,n) for(register int i=j;i<=n;i++)
#define D(i,j,n) for(register int i=j;i>=n;i--)
#define ll long long
#define lc (k<<1)
#define rc (k<<1|1)
#define N 50010
using namespace std;
namespace io{
	const int L=(1<<19)+1;
	char ibuf[L],*iS,*iT,c;int f;
	char gc(){
		if(iS==iT){
			iT=(iS=ibuf)+fread(ibuf,1,L,stdin);
			return iS==iT?EOF:*iS++;
		}
		return*iS++;
	}
	template<class I>void gi(I&x){
		for(f=1,c=gc();c<'0'||c>'9';c=gc())if(c=='-')f=-1;
		for(x=0;c<='9'&&c>='0';c=gc())x=x*10+(c&15);x*=f;
	}
};
using io::gi;
using io::gc;
int t,n,m,p,f[N],h[N];char c;
struct no{
	int l,r,t; 
	bool operator<(const no&b)const{return r<b.r;}
}x[N];
struct qwq{
	int mx[N*4],tg[N*4];
	void clear(){
		memset(mx,0,sizeof(mx));
		memset(tg,0,sizeof(tg));
	}
	void add(int k,int x){
		mx[k]+=x;tg[k]+=x; 
	}
	void add(int k,int l,int r,int p,int q,int x){
//		printf("%d %d %d %d %d %d\n",k,l,r,p,q,x); 
		if(p<=l&&r<=q){add(k,x);return;}
		add(lc,tg[k]);add(rc,tg[k]);tg[k]=0;
		int m=l+r>>1;
		if(p<=m)add(lc,l,m,p,q,x);
		if(q>m)add(rc,m+1,r,p,q,x);
		mx[k]=max(mx[lc],mx[rc]);
	}
}a[2];
int main(){
	gi(t);
	while(t--){
		gi(n);gi(m);p=1;
		a[0].clear();a[1].clear();
		F(i,1,m){
			c=0;while(c<'A'||c>'Z')c=gc();
			x[i].t=(c=='E'||c=='C');
		}
		F(i,1,m)gi(x[i].l);
		F(i,1,m)gi(x[i].r);
		sort(x+1,x+m+1);
		F(i,1,m)h[i]=n+1;
		F(i,1,n){
			while(p<=m&&x[p].r==i)
                         {if(x[p].l<x[p].r)a[x[p].t].add(1,1,n,1,x[p].l,1);p++;}
			f[i]=max(a[0].mx[1],a[1].mx[1]);
			f[i]=max(f[i],f[i-1]);
			h[f[i]]=min(h[f[i]],i);
			a[0].add(1,1,n,i,i,f[i]);a[1].add(1,1,n,i,i,f[i]);
//			printf("%d %d\n",i,f[i]); 
		}
		D(i,m,1)h[i-1]=min(h[i-1],h[i]);
		F(i,1,m)printf("%d ",h[i]<=n?h[i]:-1);puts("");
	}
	return 0;
}








In Java :





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

public class Solution {

	static int[] minimumZooNumbers(int m, int n, char[] t, int[] s, int[] d) {
		int[] counter = new int[m + 1];

		for (int i = 0; i < n; i++)
			if (s[i] < d[i])
				counter[d[i]]++;

		int[][] ind = new int[m + 1][];

		for (int i = 1; i <= m; i++)
		{
			ind[i] = new int[counter[i]];
			counter[i] = 0;
		}

		for (int i = 0; i < n; i++)
			if (s[i] < d[i])
			{
				ind[d[i]][counter[d[i]]] = i;
				counter[d[i]]++;
			}

		Node whiteRoot = buildTree(1, m);
		Node blackRoot = buildTree(1, m);

		int[] maxAnimals = new int[m + 1];

		for (int i = 1; i <= m; i++)
		{
			for (int j = 0; j < counter[i]; j++)
			{
				int k = ind[i][j];

				if (t[k] == 'E' || t[k] == 'C')
				{
					andOne(blackRoot, s[k]);
				}
				else
				{
					andOne(whiteRoot, s[k]);
				}
			}

			int max =
				Math.max(blackRoot.value + blackRoot.plus,
					whiteRoot.value + whiteRoot.plus);

			insert(blackRoot, i, max);
			insert(whiteRoot, i, max);
			maxAnimals[i] = max;
		}

		int[] res = new int[n];
		int next = 0;

		for (int i = 1; i <= m; i++)
		{
			while (next < maxAnimals[i])
			{
				res[next] = i;
				next++;
			}
		}

		while (next < n)
		{
			res[next++] = -1;
		}

		return res;
	}

	static class Node
	{
		Node left;
		Node right;
		int leftBound;
		int rightBound;
		int value = 0;
		int plus = 0;
	}

	static Node buildTree(int left, int right)
	{
		Node node = new Node();
		node.leftBound = left;
		node.rightBound = right;

		if (left == right)
		{
			return node;
		}

		int mid = (left + right) / 2;

		node.left = buildTree(left, mid);
		node.right = buildTree(mid + 1, right);

		return node;
	}

	static void andOne(Node node, int r)
	{
		if (r >= node.rightBound)
		{
			node.plus++;
			return;
		}

		if (node.plus > 0)
		{
			node.left.plus += node.plus;
			node.right.plus += node.plus;
		}

		andOne(node.left, r);

		if (r >= node.right.leftBound)
		{
			andOne(node.right, r);
		}

		updateNode(node);
	}

	static void updateNode(Node node)
	{
		node.value = Math.max(node.left.value + node.left.plus,
			node.right.value + node.right.plus);
		node.plus = 0;
	}

	static void insert(Node node, int ind, int v)
	{
		if (node.leftBound == ind && node.rightBound == ind)
		{
			node.value = v;
			node.plus = 0;
			return;
		}

		if (node.plus > 0)
		{
			node.left.plus += node.plus;
			node.right.plus += node.plus;
		}

		if (node.left.rightBound >= ind)
		{
			insert(node.left, ind, v);
		}
		else
		{
			insert(node.right, ind, v);
		}

		updateNode(node);
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int cases = in.nextInt();
		for(int a0 = 0; a0 < cases; a0++){
			int m = in.nextInt();
			int n = in.nextInt();
			char[] t = new char[n];
			for(int t_i = 0; t_i < n; t_i++){
				t[t_i] = in.next().charAt(0);
			}
			int[] s = new int[n];
			for(int s_i = 0; s_i < n; s_i++){
				s[s_i] = in.nextInt();
			}
			int[] d = new int[n];
			for(int d_i = 0; d_i < n; d_i++){
				d[d_i] = in.nextInt();
			}
			int[] result = minimumZooNumbers(m, n, t, s, d);
			for (int i = 0; i < result.length; i++) {
				System.out.print(result[i] + (i != result.length - 1 ? " " : ""));
			}
			System.out.println("");


		}
		in.close();
	}
}