HackerRank Airports Problem Solution

HackerRank Airports Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Airports Problem Solution.

Airports are being built on a straight road according to a new construction plan. For convenience, imagine a number line on which at different points airports can be positioned. Because a plane can’t take off and start landing immediately, there will be flight between two airports in locations and y if and only if x – yd, where d is a constant. Changing the position of an airport from a toy costs lay. The cost to fix a certain plan – is the minimum total cost of changing the positions of airports. After the changes, it should be possible to travel between any pair of airports, possibly taking flights through some intermediate airports. Note that it’s possible that two airports have the same initial position, and this can be the case after changes too.
On ith day, a plan to build a new airport with position, is announced. On each day that a new airport is announced, print the smallest cost to fix the set of airports announced so far . Note that you should not change the positions of any airports, just calculate the cost to do it.

Input Format
Input contains multiple queries.
The first line consists of an integer q which is the number of queries. Each query is given as
follows.
The first line of each query contains two integers n and d, the number of days, and the minimum distance respectively.
The second line of each test case contains n space-separated integers, denoting the position of the airport that was announced on ith day.

Output Format
Print one line for each query.
A line for a query with n airports should have n numbers on it where the ¿th one should be the minimum cost to fix airports in positions x1, x2,…xi,.

Sample Input 0

1
3 1
0 0 0

Sample Output 0

0 1 1

Explanation 0

The answer for a single airport is always zero. When we have many airports in the same position, it’s enough to move only one of them to satisfy the condition from the statement.

Sample Input 1

1
5 4
1 -1 2 -1 1

Sample Output 1

0 2 2 3 3

Explanation 1

For each new day that an airport is inserted, the cheapest rearranging of existing airports is shown on the diagram above. Note that cost changes for every day and travelling between airports can be done possibly flying through some intermediate ones. Costs are calculated without changing actual positions of the airports.

HackerRank Airports Problem Solution
HackerRank Airports Problem Solution

Airports C Solution

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>


typedef struct node_t{
    struct node_t *left;
    struct node_t *right;
    int value;
    int min;
    int max;
    int gap;
} node_t;

int
fix(int a, int b, int d)
{
    int dd = a > b ? a - b : b - a;
    return dd >= d ? 0 : d - dd;
}

void 
update_gap(node_t *x) 
{
    if (x == NULL) {
        return;
    }
    
    x->min = x->value;
    x->max = x->value;
    x->gap = 0;
    
    if (x->left != NULL) {
        x->min = x->left->min;
        if (x->left->gap > x->gap) {
            x->gap = x->left->gap;
        }
        int d = x->value - x->left->max;
        if (d > x->gap) {
            x->gap = d;
        }
    }
    
    if (x->right != NULL) {
        x->max = x->right->max;
        if (x->right->gap > x->gap) {
            x->gap = x->right->gap;
        }
        int d = x->right->min - x->value;
        if (d > x->gap) {
            x->gap = d;
        }
    }
}

node_t* 
node_insert(node_t *head, int value)
{
    if (head == NULL) {
        node_t *x = malloc(sizeof(node_t));
        x->left = NULL;
        x->right = NULL;
        x->value = value;
        update_gap(x);
        return x;
    }
    
    if (value > head->value) {
        node_t *x = node_insert(head->right, value);
        head->right = x;
    } else if (value < head->value) {
        node_t *x = node_insert(head->left, value);
        head->left = x;
    }

    update_gap(head);
    return head;
}

void
node_free(node_t *x)
{
    if (x != NULL) {
        node_free(x->left);
        node_free(x->right);
        free(x);
    }
}
        

node_t*
node_remove_greater_eq(node_t *x, int value)
{
    if (x == NULL) {
        return NULL;
    }
    
    if (x->value >= value) {
        node_free(x->right);
        node_t *y = node_remove_greater_eq(x->left, value);
        free(x);
        return y;
    } else {
        node_t *y = node_remove_greater_eq(x->right, value);
        x->right = y;
        update_gap(x);
        return x;
    }
}    

node_t*
node_remove_lesser_eq(node_t *x, int value)
{
    if (x == NULL) {
        return NULL;
    }
    
    if (x->value <= value) {
        node_free(x->left);
        node_t *y = node_remove_lesser_eq(x->right, value);
        free(x);
        return y;
    } else {
        node_t *y = node_remove_lesser_eq(x->left, value);
        x->left = y;
        update_gap(x);
        return x;
    }
}
    

int*
airports(int d, int n, int *x)
{
    int *rv = malloc(n * sizeof(int));
    
    rv[0] = 0;
    if (n == 1) {
        return rv;
    }
    
    int low = x[0] < x[1] ? x[0] : x[1];
    int hi = x[0] < x[1] ? x[1] : x[0];
    rv[1] = fix(x[0], x[1], d);
    if (n == 2) {
        return rv;
    }
    
    int mid_low = hi - d;
    int mid_hi = low + d;
    node_t *mid = NULL;
    
    for (int i = 2; i < n; i++) {
        int t = x[i];
        
        if (t > hi) {
            int temp = t;
            t = hi;
            hi = temp;
            mid_low = hi - d;
            mid = node_remove_lesser_eq(mid, mid_low);
        } else if (t < low) {
            int temp = t;
            t = low;
            low = temp;
            mid_hi = low + d;
            mid = node_remove_greater_eq(mid, mid_hi);
        }
        
        if (t > mid_low && t < mid_hi) {
            mid = node_insert(mid, t);
        }
    
        if (mid == NULL) {
            rv[i] = 0;
            continue;
        }
        
        int v1 = 2 * d - (hi - low) - mid->gap;
        int v2 = fix(low, mid->min, d);
        int v3 = fix(hi, mid->max, d);
        
        rv[i] = v1;
        if (v2 < rv[i]) {
            rv[i] = v2;
        }
        if (v3 < rv[i]) {
            rv[i] = v3;
        }
    }
    node_free(mid);
    return rv;
}    

int main() {
    int q; 
    scanf("%i", &q);
    for(int a0 = 0; a0 < q; a0++){
        int n; 
        int d; 
        scanf("%i %i", &n, &d);
        int *x = malloc(sizeof(int) * n);
        for (int x_i = 0; x_i < n; x_i++) {
           scanf("%i",&x[x_i]);
        }
        int result_size;
        int* result = airports(d, n, x);
        for(int result_i = 0; result_i < n; result_i++) {
            if(result_i) {
                printf(" ");
            }
            printf("%d", result[result_i]);
        }
        puts("");


    }
    return 0;
}

Airports C++ Solution

// ayy
// ' lamo
// SUBLIME HAX
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &x) {
  return os << "(" << x.first << "," << x.second << ")";
}
namespace dbg_ns {
template <typename C> struct is_iterable {
  template <class T> static long check(...);
  template <class T>
  static char check(int, typename T::const_iterator = C().end());
  enum {
    value = sizeof(check<C>(0)) == sizeof(char),
    neg_value = sizeof(check<C>(0)) != sizeof(char)
  };
};
template <class T> ostream &_out_str(ostream &os, const T &x) {
  return os << '"' << x << '"';
}
template <class T> ostream &_dbg2_5(ostream &, const T &);
template <bool B, typename T = void> using eit = typename enable_if<B, T>::type;
template <class T>
inline ostream &_dbg3(ostream &os, eit<is_iterable<T>::neg_value, const T> &x) {
  return os << x;
}
template <class T>
inline ostream &_dbg3(ostream &os, eit<is_iterable<T>::value, const T> &V) {
  os << "{";
  bool ff = 0;
  for (const auto &E : V)
    _dbg2_5(ff ? os << "," : os, E), ff = 1;
  return os << "}";
}
template <> inline ostream &_dbg3<string>(ostream &os, const string &x) {
  return _out_str(os, x);
}
template <>
inline ostream &_dbg3<const char *>(ostream &os, const char *const &x) {
  return _out_str(os, x);
}
template <class T> inline ostream &_dbg2_5(ostream &os, const T &x) {
  return _dbg3<T>(os, x);
}
template <class T, typename... Args>
ostream &_dbg2(ostream &os, vector<string>::iterator nm, const T &x,
               Args &&... args);
inline ostream &_dbg2(ostream &os, vector<string>::iterator) { return os; }
template <typename... Args>
inline ostream &_dbg2(ostream &os, vector<string>::iterator nm, const char *x,
                      Args &&... args) {
  return _dbg2(_dbg3<const char *>(os << "  ", x), nm + 1, args...);
}
template <class T, typename... Args>
inline ostream &_dbg2(ostream &os, vector<string>::iterator nm, const T &x,
                      Args &&... args) {
  return _dbg2(_dbg3<T>(os << "  " << *nm << "=", x), nm + 1, args...);
}
vector<string> split(string s) {
  vector<string> Z;
  string z = "";
  s += ',';
  int dep = 0;
  for (char c : s) {
    if (c == ',' && !dep)
      Z.push_back(z), z = "";
    else
      z += c;
    if (c == '(')
      ++dep;
    if (c == ')')
      --dep;
  }
  return Z;
}
template <typename... Args>
inline ostream &_dbg1(int ln, const string &nm, Args &&... args) {
  auto nms = split(nm);
  return _dbg2(cerr << "L" << ln << ":", nms.begin(), args...) << endl;
}
} // namespace dbg_ns
#define dbg(...) dbg_ns::_dbg1(__LINE__, #__VA_ARGS__, __VA_ARGS__)
#define sz(x) (int(x.size()))
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define pb push_back
// END SUBLIME HAX
// #include <bits/extc++.h>
// using namespace __gnu_pbds;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld; // CARE
typedef complex<ld> pt;
const ld eps = (ld)1e-8;
const ld tau = 2 * (ld)acosl(-1);
const int inf = 1e9 + 99;
const ll linf = 1e18 + 99;
const int P = 1e9 + 7;

int n;
int hi, lo;
set<int> ss;
set<pair<int, int>> ww;

void kill(int x) {
  auto it = ss.lower_bound(x);
  assert(*it == x);
  ++it;
  if (it == ss.end())
    return;
  int y = *it;
  pair<int, int> key = {y - x, x};
  if (ww.count(key))
    ww.erase(key);
}
void add(int x) {
  auto it = ss.lower_bound(x);
  assert(*it == x);
  ++it;
  if (it == ss.end())
    return;
  int y = *it;
  ww.insert({y - x, x});
}

void ins(int x) {
  auto it = ss.lower_bound(x);
  if (it != ss.end() && *it == x)
    return;
  int y = inf;
  if (it != ss.begin()) {
    --it;
    y = *it;
    kill(y);
  }
  ss.insert(x);
  if (y != inf)
    add(y);
  add(x);
}
void RZ() {
  n = 0;
  ss.clear();
  ww.clear();
}
void INS(int x) {
  if (!n) {
    hi = lo = x;
    n = 1;
    return;
  }
  if (n == 1) {
    hi = max(hi, x);
    lo = min(lo, x);
    n = 2;
    return;
  }

  ++n;
  if (x > hi) {
    ins(hi);
    hi = x;
    return;
  }
  if (x < lo) {
    ins(lo);
    lo = x;
    return;
  }
  ins(x);
}
int Q(int d) {
  if (n == 1)
    return 0;
  assert(sz(ss) <= n - 2);
  if (n == 2)
    return max(0, d - (hi - lo));

  // dbg(ss,ww,lo,hi);

  int Z = inf;
  auto it = ss.lower_bound(hi - d + 1);
  if (it == ss.end())
    return 0;
  if (*it >= lo + d)
    return 0;
  Z = min(Z, max(0, d - (*it - lo)));
  it = ss.lower_bound(lo + d);
  --it;
  Z = min(Z, max(0, d - (hi - *it)));

  for (;;) {
    auto it = ww.end();
    if (it == ww.begin()) {
      break;
    }
    --it;
    if (it->se < hi - d || it->se + it->fi > lo + d) {
      ww.erase(it);
    } else {
      break;
    }
  }
  auto it2 = ww.end();
  if (it2 != ww.begin()) {
    --it2;
    Z = min(Z, max(0, d + d - (hi - lo) - it2->fi));
  }
  return Z;
}

void _m() {
  int n, d;
  scanf("%d%d", &n, &d);
  RZ();
  for (; n--;) {
    int x;
    scanf("%d", &x);
    INS(x);
    printf("%d%c", Q(d), " \n"[!n]);
  }
}

int32_t main() {
  int q;
  scanf("%d", &q);
  for (; q--;)
    _m();
}

Airports C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {

	class II
	{
		public AA L;
		public AA R;
	}

	class AA
	{
		public int X;
		public int C;
	}

    static int[] airports(int d, int[] xx)
    {
		var rr = new int[xx.Length];
		var lx = int.MaxValue;
		var rx = int.MinValue;
		var rd = new Random();
		var aa = new OrderedSet<AA>(rd.Next, (_a, _b) => _a.X - _b.X);
		var ii = new OrderedSet<II>(rd.Next, (_a, _b) => { var _d = (_a.R.X - _a.L.X) - (_b.R.X - _b.L.X); return _d != 0 ? _d : _a.L.X - _b.L.X; });
		var a = new AA();
		var i = new II();
		for (var k = 0; k < xx.Length; ++k)
		{
			var x = xx[k];
			if (lx > x)
				lx = x;
			if (rx < x)
				rx = x;
			if (aa.Count > 0)
			{
				i.L = aa.ElementAt(0);
				while (i.L.X <= rx - d)
				{
					aa.Remove(i.L);
					if (aa.Count == 0)
						break;
					i.R = aa.ElementAt(0);
					ii.Remove(i);
					i.L = i.R;
				}
			}
			if (aa.Count > 0)
			{
				i.R = aa.ElementAt(aa.Count - 1);
				while (i.R.X >= lx + d)
				{
					aa.Remove(i.R);
					if (aa.Count == 0)
						break;
					i.L = aa.ElementAt(aa.Count - 1);
					ii.Remove(i);
					i.R = i.L;
				}
			}
			if (x > rx - d && x < lx + d)
			{
				if (aa.Count == 0)
					aa.Add(new AA() { X = x, C = 1 });
				else
				{
					a.X = x;
					var j = aa.IndexOf(a);
					if (j >= 0)
						++aa.ElementAt(j).C;
					else
					{
						j = ~j;
						var b = new AA() { X = x, C = 1 };
						if (j == aa.Count)
						{
							ii.Add(new II()
							{
								L = aa.ElementAt(j - 1),
								R = b
							});
							aa.Add(b);
						}
						else if (j == 0)
						{
							ii.Add(new II()
							{
								L = b,
								R = aa.ElementAt(j)
							});
							aa.Add(b);
						}
						else
						{
							i.L = aa.ElementAt(j - 1);
							i.R = aa.ElementAt(j);
							ii.Remove(i);
							ii.Add(new II()
							{
								L = i.L,
								R = b
							});
							ii.Add(new II()
							{
								L = b,
								R = i.R
							});
							aa.Add(b);
						}
					}
				}
			}
			if (lx + d <= rx - d || aa.Count == 0)
				rr[k] = 0;
			else if (lx == rx)
			{
				var c = aa.ElementAt(0);
				rr[k] = c.C == 1 ? 0 : d;
			}
			else if (aa.Count == 1)
			{
				var c = aa.ElementAt(0);
				var lp = d - (c.X - lx);
				var rp = d - (rx - c.X);
				rr[k] = Math.Min(lp, rp);
			}
			else
			{
				var l = aa.ElementAt(0);
				var r = aa.ElementAt(aa.Count - 1);
				var m = ii.ElementAt(ii.Count - 1);
				if (l.X != lx)
				{
					var lp = d - (l.X - lx);
					var rp = d - (rx - r.X);
					var mp = d - (rx - m.L.X) + d - (m.R.X - lx);
					rr[k] = Math.Min(mp, Math.Min(lp, rp));
				}
				else if ((m.L.X == lx && m.L.C == 1) || (m.R.X == rx && m.R.C == 1))
					rr[k] = d - (m.R.X - m.L.X);
				else
				{
					var lp = d - (l.C > 1 ? 0 : aa.ElementAt(1).X - l.X);
					var rp = d - (r.C > 1 ? 0 : r.X - aa.ElementAt(aa.Count - 2).X);
					var mp = d - (rx - m.L.X) + d - (m.R.X - lx);
					rr[k] = Math.Min(mp, Math.Min(lp, rp));
				}
			}
		}
		return rr;
    }

    static void Main(String[] args) {
        int q = Convert.ToInt32(Console.ReadLine());
        for(int a0 = 0; a0 < q; a0++){
            string[] tokens_n = Console.ReadLine().Split(' ');
            int n = Convert.ToInt32(tokens_n[0]);
            int d = Convert.ToInt32(tokens_n[1]);
            string[] x_temp = Console.ReadLine().Split(' ');
            int[] x = Array.ConvertAll(x_temp,Int32.Parse);
            int[] result = airports(d, x);
            Console.WriteLine(String.Join(" ", result));


        }
    }
}

class OrderedSet<E>
{
	public OrderedSet(Func<int> getPriority, Func<E, E, int> compareElements)
	{
		Configure(getPriority, compareElements);
	}

	public void Clear()
	{
		root = null;
	}

	public void Configure(Func<int> getPriority, Func<E, E, int> compareElements)
	{
		if (getPriority == null || compareElements == null)
			throw new ArgumentNullException();
		Clear();
		GetPriority = getPriority;
		CompareElements = compareElements;
	}

	public int Count
	{
		get
		{
			return CountOf(root);
		}
	}

	public E ElementAt(int index)
	{
		if (index < 0 || index >= CountOf(root))
			throw new IndexOutOfRangeException();
		return NodeAt(index).Element;
	}

	Node NodeAt(int index)
	{
		var t = root;
		while (true)
		{
			var i = CountOf(t.Left);
			if (i == index)
				break;
			if (index < i)
				t = t.Left;
			else
			{
				index -= 1 + i;
				t = t.Right;
			}
		}
		return t;
	}

	public int IndexOf(E element)
	{
		var i = 0;
		var t = root;
		while (t != null)
		{
			var c = CompareElements(element, t.Element);
			if (c < 0)
				t = t.Left;
			else
			{
				i += 1 + CountOf(t.Left);
				if (c == 0)
					break;
				t = t.Right;
			}
		}
		return t == null ? ~i : i - 1;
	}

	public bool Add(E element)
	{
		var o = GetPriority();
		var b = 0;
		Node p = null;
		Node q = null;
		var t = root;
		while (t != null)
		{
			var c = CompareElements(element, t.Element);
			if (c == 0)
				return false;
			if (o <= t.Priority)
			{
				p = t;
				b = c;
			}
			else if (q == null)
				q = t;
			t = c < 0 ? t.Left : t.Right;
		}
		var count = checked(Count + 1);
		var n = new Node()
		{
			Element = element,
			Priority = o,
			Count = 1
		};
		if (q != null)
		{
			Split(q, element, true, out n.Left, out n.Right);
			if (n.Left != null)
			{
				n.Left.Parent = n;
				n.Count += n.Left.Count;
			}
			if (n.Right != null)
			{
				n.Right.Parent = n;
				n.Count += n.Right.Count;
			}
		}
		if (p == null)
			root = n;
		else
		{
			if (b < 0)
				p.Left = n;
			else
				p.Right = n;
			n.Parent = p;
			while ((n = n.Parent) != null)
				++n.Count;
		}
		return true;
	}

	public bool Remove(E element)
	{
		Node p = null;
		var t = root;
		while (true)
		{
			if (t == null)
				return false;
			var c = CompareElements(element, t.Element);
			if (c == 0)
				break;
			p = t;
			t = c < 0 ? t.Left : t.Right;
		}
		var n = Merge(t.Left, t.Right);
		if (p == null)
			root = n;
		else
		{
			if (p.Left == t)
				p.Left = n;
			else
				p.Right = n;
			if (n != null)
				n.Parent = p;
			for (; p != null; p = p.Parent)
				--p.Count;
		}
		return true;
	}

	Node Merge(Node left, Node right)
	{
		if (left == null)
		{
			if (right != null)
				right.Parent = null;
			return right;
		}
		if (right == null)
		{
			if (left != null)
				left.Parent = null;
			return left;
		}
		var e = false;
		Node r = null;
		Node p = null;
		if (left.Priority >= right.Priority)
		{
			r = left;
			e = true;
			p = left;
			p.Count += right.Count;
			left = left.Right;
		}
		else
		{
			r = right;
			e = false;
			p = right;
			p.Count += left.Count;
			right = right.Left;
		}
		r.Parent = null;
		while (true)
		{
			if (right == null)
			{
				if (!e)
				{
					p.Left = left;
					left.Parent = p;
				}
				break;
			}
			if (left == null)
			{
				if (e)
				{
					p.Right = right;
					right.Parent = p;
				}
				break;
			}
			if (left.Priority >= right.Priority)
			{
				if (!e)
				{
					e = true;
					p.Left = left;
					left.Parent = p;
				}
				p = left;
				p.Count += right.Count;
				left = left.Right;
			}
			else
			{
				if (e)
				{
					e = false;
					p.Right = right;
					right.Parent = p;
				}
				p = right;
				p.Count += left.Count;
				right = right.Left;
			}
		}
		return r;
	}

	void Split(Node t, E element, bool isLeft, out Node left, out Node right)
	{
		left = null;
		right = null;
		Node l = null;
		Node r = null;
		while (t != null)
		{
			var c = CompareElements(t.Element, element);
			if (c < 0 || (c == 0 && isLeft))
			{
				if (l == null)
					left = t;
				else
					l.Right = t;
				t.Parent = l;
				l = t;
				t = t.Right;
			}
			else
			{
				if (r == null)
					right = t;
				else
					r.Left = t;
				t.Parent = r;
				r = t;
				t = t.Left;
			}
		}
		if (l != null)
			l.Right = null;
		if (r != null)
			r.Left = null;
		PropagateUpwards(l);
		PropagateUpwards(r);
	}

	void PropagateUpwards(Node t, Node a = null)
	{
		for (; t != a; t = t.Parent)
			t.Count = 1 + CountOf(t.Left) + CountOf(t.Right);
	}

	static int CountOf(Node t)
	{
		return t == null ? 0 : t.Count;
	}

	class Node
	{
		public E Element;
		public int Priority;
		public int Count;
		public Node Parent;
		public Node Left;
		public Node Right;
	}

	Node root;
	Func<int> GetPriority;
	Func<E, E, int> CompareElements;
}

Airports Java Solution

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

public class Solution {

  static class Gap {
    int start;
    int size;
    int end;
    boolean outdated = false;

    Gap(int start, int size) {
      this.start = start;
      this.size = size;
      this.end = start + size - 1;
    }

    void split(int cut) {
      if (size == 1) {
        return;
      }
      if (cut == start) {
        Gap split = new Gap(start + 1, size - 1);
        gaps.add(split);
        topGaps.add(split);
        return;
      }
      if (cut == start + size - 1) {
        Gap split = new Gap(start, size - 1);
        gaps.add(split);
        topGaps.add(split);
        return;
      }
      Gap split = new Gap(start, cut - start);
      gaps.add(split);
      topGaps.add(split);
      split = new Gap(cut + 1, size - (cut - start) - 1);
      gaps.add(split);
      topGaps.add(split);
    }

    public int getStart() {
      return start;
    }

    public int getSize() {
      return size;
    }
  }
  
  static int d;
  static int[] positions;
  static int index = 0;
  static int minIndex;
  static int maxIndex;
  static TreeSet<Gap> gaps = new TreeSet<>(Comparator.comparing(Gap::getStart));
  static PriorityQueue<Gap> topGaps = new PriorityQueue<>(Comparator.comparing(Gap::getSize).reversed());
  static int oldLeft;
  static int oldRight;

  static void init() {
    minIndex = 0;
    maxIndex = 0;
    index = 0;
    gaps.clear();
    topGaps.clear();
    Gap rootGap = new Gap(-1000000000, 2000000000);
    gaps.add(rootGap);
    topGaps.add(rootGap);
    oldLeft = -1000000000;
    oldRight = 1000000000;
  }

  static int solveNext() {
    int x = positions[index++];

    if (index == 1) {
      return 0;
    }

    int newSplitPoint = Integer.MAX_VALUE;
    if (x < positions[minIndex]) {
      if (minIndex != maxIndex) {
        newSplitPoint = positions[minIndex];
      }
      minIndex = index - 1;
    } else if (x > positions[maxIndex]) {
      if (minIndex != maxIndex) {
        newSplitPoint = positions[maxIndex];
      }
      maxIndex = index - 1;
    } else {
      newSplitPoint = x;
    }

    if (positions[maxIndex] - positions[minIndex] >= 2 * d - 1) {
      return 0;
    }

    int left = positions[maxIndex] - d + 1;
    if (left > oldLeft) {
      for (Iterator<Gap> iterator = gaps.iterator(); iterator.hasNext();) {
        Gap gap = iterator.next();
        if (left <= gap.start) {
          break;
        }
        gap.outdated = true;
        iterator.remove();
        if (left < gap.start + gap.size) {
          Gap newGap = new Gap(left, gap.size - (left - gap.start));
          gaps.add(newGap);
          topGaps.add(newGap);
          break;
        }
      }
      oldLeft = left;
    }

  int right = positions[minIndex] + d - 1;
    if (right < oldRight) {
      for (Iterator<Gap> iterator = gaps.descendingIterator(); iterator.hasNext();) {
        Gap gap = iterator.next();
        if (right >= gap.end) {
          break;
        }
        gap.outdated = true;
        iterator.remove();
        if (right >= gap.start) {
          Gap newGap = new Gap(gap.start, right - gap.start + 1);
          gaps.add(newGap);
          topGaps.add(newGap);
          break;
        }
      }
      oldRight = right;
    }

    if (newSplitPoint >= left && newSplitPoint <= right) {
      Gap floor = gaps.floor(new Gap(newSplitPoint, 0));
      if (floor != null) {
        if (newSplitPoint <= floor.end) {
          floor.outdated = true;
          gaps.remove(floor);
          floor.split(newSplitPoint);
        }
      }
    }

    if (index == 2) {
      return Math.max(0, d - (positions[maxIndex] - positions[minIndex]));
    }

    while (!topGaps.isEmpty() && topGaps.peek().outdated) {
      topGaps.poll();
    }

    return right - left + 1 - (topGaps.isEmpty() ? 0 : topGaps.peek().size);
  }
  
  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 t = Integer.parseInt(st.nextToken());
    
    for (int i = 0; i < t; i++) {
      st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      d = Integer.parseInt(st.nextToken());
      positions = new int[n];
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < n; j++) {
        positions[j] = Integer.parseInt(st.nextToken());
      }
      init();
      for (int j = 0; j < n; j++) {
        int res = solveNext();
        bw.write(res + " ");
      }
      bw.write('\n');
    }

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

Airports Python Solution

import math
import os
import random
import re
import sys
from heapq import heappop, heappush, heapify

#
# Complete the 'airports' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts following parameters:
#  1. INTEGER d
#  2. INTEGER_ARRAY x
#


def airports(min_dist, airports):
    road = sorted(set(airports))
    len_road = len(road)
    answers = []
    airport_indices = dict()
    for i, a in enumerate(road):
        airport_indices[a] = i    
    qty = [0] * len_road
    for a in airports:
        qty[airport_indices[a]] += 1
    safe = []
    near_left = []
    near_right = []
    near_both = []
    for i in range(len_road - 1):
        gap = (i, i + 1)
        safe.append(gap)
    heapify(near_left)
    heapify(near_right)
    heapify(near_both)
    left_airport = 0
    right_airport = len_road - 1
    second_left = 1
    second_right = len_road - 2
    next_airport = list(range(1, len_road)) + ['N']
    prev_airport = ['N'] + list(range(len_road - 1))
    for ap in reversed(airports):
        road_left_airport, road_right_airport = road[left_airport], road[right_airport]
        while safe and (road[safe[-1][1]] - road_left_airport < min_dist or road_right_airport - road[safe[-1][0]] < min_dist):
            gap = safe.pop()
            if road[gap[1]] - road_left_airport < min_dist:
                heappush(near_left,(0 - road[gap[1]],gap))
            else:
                heappush(near_right,(road[gap[0]],gap))
        while near_left and road_right_airport - road[near_left[0][1][0]] < min_dist:
            gap = heappop(near_left)[1]
            heappush(near_both,(road[gap[0]] - road[gap[1]], gap))
        while near_right and road[near_right[0][1][1]] - road_left_airport < min_dist:
            gap = heappop(near_right)[1]
            heappush(near_both,(road[gap[0]] - road[gap[1]], gap))
        while near_both and (near_both[0][1][0] < left_airport or near_both[0][1][1] > right_airport):
            heappop(near_both)
        if safe:
            answers.append(0)
        else:
            possible_answers = [min_dist]
            if left_airport != right_airport:
                if qty[left_airport] == 1:
                    possible_answers.append(min_dist + road_left_airport - road[second_left])
                if qty[right_airport] == 1:
                    possible_answers.append(min_dist + road[second_right] - road_right_airport)
            if near_left:
                possible_answers.append(max(0, min_dist + road_left_airport - road[near_left[0][1][1]]))
            if near_right:
                possible_answers.append(max(0, min_dist + road[near_right[0][1][0]] - road_right_airport))
            if near_both:
                possible_answers.append(0)
                nb = near_both[0][1]
                possible_answers[-1] += max(0,min_dist + road_left_airport - road[nb[1]])
                possible_answers[-1] += max(0,min_dist + road[nb[0]] - road_right_airport)
            answers.append(min(possible_answers))
        ai = airport_indices[ap]
        qty[ai] -= 1
        if qty[ai]:
            continue
        while second_left < len_road - 1 and qty[second_left] == 0:
            second_left += 1
        while second_right > 0 and qty[second_right] == 0:
            second_right -= 1  
        if ai == left_airport or ai == right_airport:
            while left_airport < len_road - 1 and qty[left_airport] == 0:
                left_airport += 1
            while right_airport > 0 and qty[right_airport] == 0:
                right_airport -= 1
            second_left = max(second_left, left_airport + 1)
            second_right = min(second_right, right_airport - 1)
            while second_left < len_road - 1 and qty[second_left] == 0:
                second_left += 1
            while second_right > 0 and qty[second_right] == 0:
                second_right -= 1   
        else:
            l = prev_airport[ai]
            r = next_airport[ai]
            next_airport[l] = r
            prev_airport[r] = l
            gap = (l, r)
            safe.append(gap)    
    answers.reverse()
    answers[0] = 0
    return answers

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    q = int(input().strip())
    for q_itr in range(q):
        first_multiple_input = input().rstrip().split()
        n = int(first_multiple_input[0])
        d = int(first_multiple_input[1])
        x = list(map(int, input().rstrip().split()))
        result = airports(d, x)
        fptr.write(' '.join(map(str, result)))
        fptr.write('\n')
    fptr.close()
c C# C++ HackerRank Solutions java python