HackerRank Animal Transport problem solution

In this 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 i, Capeta knows its type ti (E for elephant, D for dog, C for cat and M for mouse), source zoo si where Capeta has to pick it up from, and destination zoo di 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:

He must visit the zoos in increasing order. He also cannot skip zoos.

Dogs are scared of elephants, so he is not allowed to bring them together at the same time.

Cats are scared of dogs, so he is not allowed to bring them together at the same time.
Mice are scared of cats, so he is not allowed to bring them together at the same time.
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 x animals, for each x from 1 to n.

Complete the function minimumZooNumbers and return an integer array where the xth integer is the minimum number of zoos that Capeta needs to reach so that she is able to transport x animals, or -1 if it is impossible to transport animals.

HackerRank Animal Transport problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

  static class LazySegment {
    int n;
    int h;
    int[] a;
    int[] f;

    public LazySegment(int n) {
      this.n = n;
      h = 32 - Integer.numberOfLeadingZeros(n);
      int base = (1 << h);
      a = new int[base << 1];
      f = new int[base << 1];
    }

    void rangeApply(int l, int r, int z) {
      rangeApply(0, 0, n, l, r, z);
    }

    void rangeApply(int i, int il, int ir, int l, int r, int z) {
      if (l <= il && ir <= r) {
        a[i] = z + a[i];
        if (i < f.length) {
          f[i] = z + f[i];
        }
      } else if (ir <= l || r <= il) {

      } else {
        rangeApply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);
        rangeApply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);
        f[i] = 0;
        rangeApply(2 * i + 1, il, (il + ir) / 2, l, r, z);
        rangeApply(2 * i + 2, (il + ir) / 2, ir, l, r, z);
        a[i] = Math.max(a[2 * i + 1], a[2 * i + 2]);
      }
    }

    int rangeConcat(int l, int r) {
      return rangeConcat(0, 0, n, l, r);
    }

    int rangeConcat(int i, int il, int ir, int l, int r) {
      if (l <= il && ir <= r) {
        return a[i];
      } else if (ir <= l || r <= il) {
        return 0;
      } else {
        return f[i]
            + Math.max(
                rangeConcat(2 * i + 1, il, (il + ir) / 2, l, r),
                rangeConcat(2 * i + 2, (il + ir) / 2, ir, l, r));
      }
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int cases = Integer.parseInt(st.nextToken());

    for (int itr = 0; itr < cases; itr++) {
      st = new StringTokenizer(br.readLine());
      int m = Integer.parseInt(st.nextToken());
      int n = Integer.parseInt(st.nextToken());

      char[] t = new char[n];
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++) {
        char item = st.nextToken().charAt(0);
        t[i] = item;
      }

      int[] s = new int[n];
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++) {
        int item = Integer.parseInt(st.nextToken());
        s[i] = item - 1;
      }

      int[] d = new int[n];
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++) {
        int item = Integer.parseInt(st.nextToken());
        d[i] = item - 1;
      }
      @SuppressWarnings("unchecked")
      List<Integer>[] fromD = new List[m];
      for (int i = 0; i < n; i++) {
        if (s[i] < d[i]) {
          if (fromD[d[i]] == null) {
            fromD[d[i]] = new ArrayList<>();
          }
          fromD[d[i]].add(i);
        }
      }

      LazySegment segtree0 = new LazySegment(m + 1);
      LazySegment segtree1 = new LazySegment(m + 1);
      int[] dp = new int[m];
      for (int x = 0; x < m; x++) {
        if (fromD[x] != null) {
          for (int i : fromD[x]) {
            if (t[i] == 'E' || t[i] == 'C') {
              segtree0.rangeApply(0, s[i] + 1, 1);
            } else {
              segtree1.rangeApply(0, s[i] + 1, 1);
            }
          }
        }
        dp[x] = Math.max(segtree0.rangeConcat(0, x + 1), segtree1.rangeConcat(0, x + 1));
        segtree0.rangeApply(x, x + 1, dp[x]);
        segtree1.rangeApply(x, x + 1, dp[x]);
      }

      int y = 1;
      for (int x = 0; ; y++) {
        while (x < m && dp[x] < y) {
          x++;
        }
        if (x == m) {
          break;
        }
        bw.write((x + 1) + " ");
      }
      for (; y <= n; y++) {
        bw.write(y < n ? "-1 " : "-1");
      }

      bw.newLine();
    }

    bw.close();
    br.close();
  }
}

Animal Transport problem solution in C++.

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP_R(i, n) for (int i = (n) - 1; (i) >= 0; -- (i))
using namespace std;
 
template <class Monoid, class OperatorMonoid>
struct lazy_propagation_segment_tree { // on monoids
    static_assert (is_same<typename Monoid::underlying_type, typename OperatorMonoid::target_type>::value, "");
    typedef typename Monoid::underlying_type underlying_type;
    typedef typename OperatorMonoid::underlying_type operator_type;
    Monoid mon;
    OperatorMonoid op;
    int n;
    vector<underlying_type> a;
    vector<operator_type> f;
    lazy_propagation_segment_tree() = default;
    lazy_propagation_segment_tree(int a_n, underlying_type initial_value = Monoid().unit(), Monoid const & a_mon = Monoid(), OperatorMonoid const & a_op = OperatorMonoid())
            : mon(a_mon), op(a_op) {
        n = 1; while (n <= a_n) n *= 2;
        a.resize(2 * n - 1, mon.unit());
        fill(a.begin() + (n - 1), a.begin() + ((n - 1) + a_n), initial_value); // set initial values
        REP_R (i, n - 1) a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]); // propagate initial values
        f.resize(max(0, (2 * n - 1) - n), op.identity());
    }
    void point_set(int i, underlying_type z) {
        assert (0 <= i and i < n);
        point_set(0, 0, n, i, z);
    }
    void point_set(int i, int il, int ir, int j, underlying_type z) {
        if (i == n + j - 1) { // 0-based
            a[i] = z;
        } else if (ir <= j or j+1 <= il) {
            // nop
        } else {
            range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);
            range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);
            f[i] = op.identity();
            point_set(2 * i + 1, il, (il + ir) / 2, j, z);
            point_set(2 * i + 2, (il + ir) / 2, ir, j, z);
            a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]);
        }
    }
    void range_apply(int l, int r, operator_type z) {
        assert (0 <= l and l <= r and r <= n);
        range_apply(0, 0, n, l, r, z);
    }
    void range_apply(int i, int il, int ir, int l, int r, operator_type z) {
        if (l <= il and ir <= r) { // 0-based
            a[i] = op.apply(z, a[i]);
            if (i < f.size()) f[i] = op.compose(z, f[i]);
        } else if (ir <= l or r <= il) {
            // nop
        } else {
            range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);
            range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);
            f[i] = op.identity();
            range_apply(2 * i + 1, il, (il + ir) / 2, l, r, z);
            range_apply(2 * i + 2, (il + ir) / 2, ir, l, r, z);
            a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]);
        }
    }
    underlying_type range_concat(int l, int r) {
        assert (0 <= l and l <= r and r <= n);
        return range_concat(0, 0, n, l, r);
    }
    underlying_type range_concat(int i, int il, int ir, int l, int r) {
        if (l <= il and ir <= r) { // 0-based
            return a[i];
        } else if (ir <= l or r <= il) {
            return mon.unit();
        } else {
            return op.apply(f[i], mon.append(
                    range_concat(2 * i + 1, il, (il + ir) / 2, l, r),
                    range_concat(2 * i + 2, (il + ir) / 2, ir, l, r)));
        }
    }
};
struct max_monoid {
    typedef int underlying_type;
    int unit() const { return 0; }
    int append(int a, int b) const { return max(a, b); }
};
struct plus_operator_monoid {
    typedef int underlying_type;
    typedef int target_type;
    int identity() const { return 0; }
    int apply(underlying_type a, target_type b) const { return a + b; }
    int compose(underlying_type a, underlying_type b) const { return a + b; }
};
typedef lazy_propagation_segment_tree<max_monoid, plus_operator_monoid> starry_sky_tree;
 
int main() {
    int testcase; scanf("%d", &testcase);
    while (testcase --) {
        // input
        int m, n; scanf("%d%d", &m, &n);
        vector<char> t(n); REP (i, n) scanf(" %c", &t[i]);
        vector<int> s(n); REP (i, n) { scanf("%d", &s[i]); -- s[i]; }
        vector<int> d(n); REP (i, n) { scanf("%d", &d[i]); -- d[i]; }
        // solve
        vector<vector<int> > from_d(m);
        REP (i, n) {
            if (s[i] < d[i]) {
                from_d[d[i]].push_back(i);
            }
        }
        vector<int> dp(m);
        array<starry_sky_tree, 2> segtree;
        REP (p, 2) segtree[p] = starry_sky_tree(m + 1);
        REP (x, m) {
            for (int i : from_d[x]) {
                const char *table = "EDCM";
                int p = (strchr(table, t[i]) - table) % 2;
                segtree[p].range_apply(0, s[i] + 1, 1);
            }
            dp[x] = max(
                segtree[0].range_concat(0, x + 1),
                segtree[1].range_concat(0, x + 1));
            REP (p, 2) {
                segtree[p].range_apply(x, x + 1, dp[x]);
            }
        }
        // output
        int y = 1;
        for (int x = 0; ; ++ y) {
            while (x < m and dp[x] < y) ++ x;
            if (x == m) break;
            printf("%d ", x + 1);
        }
        for (; y <= n; ++ y) printf("-1%c", y < n ? ' ' : 'n');
    }
    return 0;
}

Problem solution in C.

#include<stdio.h>
#include<stdlib.h>
typedef struct _node
{
    int max;
    int off;
}node;
typedef struct _lnode
{
    int x;
    struct _lnode *next;
}lnode;
char str[2];
int t[50000], s[50000], d[50000], ans[3][50000];
node tree[2][200000];
lnode *table[2][50000];
void push(int v, int tl, int tr, node *t)
{
    if(t[v].off)
    {
        t[v].max += t[v].off;
        if( tl != tr )
        {
            t[2*v].off += t[v].off;
            t[2*v+1].off += t[v].off;
        }
        t[v].off = 0;
    }
    return;
}
int sum(int v, int tl, int tr, int l, int r, node *t)
{
    int tm;
    push(v, tl, tr, t);
    if( tr < l || tl > r )
    {
        return 0;
    }
    if( tl >= l && tr <= r )
    {
        return t[v].max;
    }
    tm = ( tl + tr ) / 2;
    return max(sum(2*v, tl, tm, l, r, t), sum(2*v+1, tm+1, tr, l, r, t));
}
void range_update(int v, int tl, int tr, int pos1, int pos2, long long new_val, node *t)
{
    int tm;
    push(v, tl, tr, t);
    if( pos2 < tl || pos1 > tr )
    {
        return;
    }
    if( pos1 <= tl && pos2 >= tr )
    {
        t[v].off += new_val;
    }
    else
    {
        tm = ( tl + tr ) / 2;
        range_update(2*v, tl, tm, pos1, pos2, new_val, t);
        range_update(2*v+1, tm+1, tr, pos1, pos2, new_val, t);
        push(2*v, tl, tm, t);
        push(2*v+1, tm+1, tr, t);
        t[v].max = max(t[2*v].max, t[2*v+1].max);
    }
    return;
}
int max(int x, int y)
{
    return x > y ? x : y;
}
void clean_table(lnode **table)
{
    int i;
    lnode *p, *pp;
    for( i = 0 ; i < 50000 ; i++ )
    {
        if(table[i])
        {
            p = table[i];
            while(p)
            {
                pp = p -> next;
                free(p);
                p = pp;
            }
            table[i] = NULL;
        }
    }
    return;
}
void insert_edge(int x, int y, lnode **table)
{
    lnode *t = malloc(sizeof(lnode));
    t -> x = y;
    t -> next = table[x];
    table[x] = t;
    return;
}
int main()
{
    int T, m, n, i, j;
    lnode *p;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &m, &n);
        for( i = 0 ; i < n ; i++ )
        {
            scanf("%s", str);
            if( str[0] == 'E' || str[0] == 'C' )
            {
                t[i] = 0;
            }
            else
            {
                t[i] = 1;
            }
        }
        for( i = 0 ; i < n ; i++ )
        {
            scanf("%d", s + i);
        }
        for( i = 0 ; i < n ; i++ )
        {
            scanf("%d", d + i);
        }
        for( i = 0 ; i < n ; i++ )
        {
            if( d[i] > s[i] )
            {
                insert_edge(d[i]-1, s[i]-1, &table[t[i]][0]);
            }
        }
        for( i = 0 ; i < m ; i++ )
        {
            for( p = table[0][i] ; p ; p = p -> next )
            {
                range_update(1, 0, m-1, 0, p -> x, 1, &tree[0][0]);
            }
            for( p = table[1][i] ; p ; p = p -> next )
            {
                range_update(1, 0, m-1, 0, p -> x, 1, &tree[1][0]);
            }
            ans[0][i] = sum(1, 0, m-1, 0, i, &tree[0][0]);
            ans[1][i] = sum(1, 0, m-1, 0, i, &tree[1][0]);
            ans[2][i] = max(ans[0][i], ans[1][i]);
            range_update(1, 0, m-1, i, i, ans[2][i], &tree[0][0]);
            range_update(1, 0, m-1, i, i, ans[2][i], &tree[1][0]);
        }
        for( i = 1, j = 0 ; i <= n ; i++ )
        {
            while( ans[2][j] < i && j < m )
            {
                j++;
            }
            if( j == m )
            {
                printf("-1 ");
            }
            else
            {
                printf("%d ", j + 1);
            }
        }
        printf("n");
        memset(ans, 0, sizeof(ans));
        memset(tree, 0, sizeof(tree));
        clean_table(&table[0][0]);
        clean_table(&table[1][0]);
    }
    return 0;
}