In this HackerRank Animal Transport problem solution, we need to 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 x animals.
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();
}
}
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;
}
0 Comments