Two Platforms (Codeforces 1409E)
Tags: DP, two pointers

There are $$$n$$$ points on a plane. The $$$i$$$-th point has coordinates $$$(x_i, y_i)$$$. You have two horizontal platforms, both of length $$$k$$$. Each platform can be placed anywhere on a plane but it should be placed horizontally (on the same $$$y$$$-coordinate) and have integer borders. If the left border of the platform is $$$(x, y)$$$ then the right border is $$$(x + k, y)$$$ and all points between borders (including borders) belong to the platform.Note that platforms can share common points (overlap) and it is not necessary to place both platforms on the same $$$y$$$-coordinate.When you place both platforms on a plane, all points start falling down decreasing their $$$y$$$-coordinate. If a point collides with some platform at some moment, the point stops and is saved. Points which never collide with any platform are lost.Your task is to find the maximum number of points you can save if you place both platforms optimally.You have to answer $$$t$$$ independent test cases.For better understanding, please read the Note section below to see a picture for the first test case.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.The first line of the test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^9$$$) — the number of points and the length of each platform, respectively. The second line of the test case contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_i \le 10^9$$$), where $$$x_i$$$ is $$$x$$$-coordinate of the $$$i$$$-th point. The third line of the input contains $$$n$$$ integers $$$y_1, y_2, \dots, y_n$$$ ($$$1 \le y_i \le 10^9$$$), where $$$y_i$$$ is $$$y$$$-coordinate of the $$$i$$$-th point. All points are distinct (there is no pair $$$1 \le i < j \le n$$$ such that $$$x_i = x_j$$$ and $$$y_i = y_j$$$).It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Output: For each test case, print the answer: the maximum number of points you can save if you place both platforms optimally.

Note: The picture corresponding to the first test case of the example:Blue dots represent the points, red segments represent the platforms. One of the possible ways is to place the first platform between points $$$(1, -1)$$$ and $$$(2, -1)$$$ and the second one between points $$$(4, 3)$$$ and $$$(5, 3)$$$. Vectors represent how the points will fall down. As you can see, the only point we can't save is the point $$$(3, 7)$$$ so it falls down infinitely and will be lost. It can be proven that we can't achieve better answer here. Also note that the point $$$(5, 3)$$$ doesn't fall at all because it is already on the platform.

Sample Inputs:
4
7 1
1 5 2 3 1 5 4
1 3 6 7 2 5 4
1 1
1000000000
1000000000
5 10
10 7 5 15 8
20 199 192 219 1904
10 10
15 19 8 17 20 10 9 2 10 19
12 13 6 17 1 14 7 9 19 3

Sample Outputs:
6
1
5
10

Solution (Python):
import collections
import math
import os
import random
import sys
from bisect import bisect, bisect_left
from functools import reduce
from heapq import heapify, heappop, heappush
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ints = lambda : list(map(int, input().split()))

def printQry(a, b) -> None:
    sa = str(a)
    sb = str(b)
    print(f'? {sa} {sb}', flush=True)

def printAns(ans) -> None:
    s = str(ans)
    print(f'! {s}', flush=True)

def solve() -> None:
    (n, k) = map(int, input().split())
    x = ints()
    y = ints()
    ans = 0
    x.sort()
    save = [0] * n
    l = 0
    for r in range(n):
        while x[r] - x[l] > k:
            l += 1
        save[r] = max(r - l + 1, save[r - 1])
        ans = max(ans, r - l + 1 if l == 0 else r - l + 1 + save[l - 1])
    ''
    print(ans)
t = int(input())
for _ in range(t):
    solve()

Solution (Python):
for _ in range(int(input())):
    (n, k) = list(map(int, input().split()))
    (nums, _) = (sorted(map(int, input().split())), list(map(int, input().split())))
    if 2 * k >= nums[-1] - nums[0]:
        print(len(nums))
        continue
    f = [0] * (n + 1)
    l = ans = 0
    for (r, v) in enumerate(nums):
        while v - nums[l] > k:
            l += 1
        f[r + 1] = max(f[r], r - l + 1)
        ans = max(ans, f[l] + r - l + 1)
    print(ans)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())

def digitSum(x):
    c = 0
    while x:
        c += x % 10
        x //= 10
    return c

def solve(k, numbers):
    if not numbers:
        return 0
    numbers.sort()
    low = 0
    high = -1
    best = [1 for i in range(len(numbers))]
    overallBest = 0
    for (n, i) in enumerate(numbers):
        while low <= high and i - k > numbers[low]:
            low += 1
        if low > high:
            high += 1
        elif i - numbers[low] <= k:
            high += 1
        length = high - low + 1
        if n > 0:
            best[n] = max(best[n - 1], length)
        if n >= length:
            overallBest = max(overallBest, length + best[n - length])
        else:
            overallBest = best[n]
    return overallBest
lines = inp()
for i in range(lines):
    v = inlt()
    w = inlt()
    _ = inlt()
    print(solve(v[1], w))