Rectangle Shrinking (Codeforces 1782E)
Tags: Greedy, sortings

You have a rectangular grid of height $$$2$$$ and width $$$10^9$$$ consisting of unit cells. There are $$$n$$$ rectangles placed on this grid, and the borders of these rectangles pass along cell borders. The $$$i$$$-th rectangle covers all cells in rows from $$$u_i$$$ to $$$d_i$$$ inclusive and columns from $$$l_i$$$ to $$$r_i$$$ inclusive ($$$1 \le u_i \le d_i \le 2$$$; $$$1 \le l_i \le r_i \le 10^9$$$). The initial rectangles can intersect, be nested, and coincide arbitrarily.You should either remove each rectangle, or replace it with any of its non-empty subrectangles. In the latter case, the new subrectangle must lie inside the initial rectangle, and its borders must still pass along cell borders. In particular, it is allowed for the subrectangle to be equal to the initial rectangle.After that replacement, no two (non-removed) rectangles are allowed to have common cells, and the total area covered with the new rectangles must be as large as possible.  Illustration for the first test case. The initial rectangles are given at the top, the new rectangles are given at the bottom. Rectangle number $$$4$$$ is removed. 

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of rectangles.Each of the next $$$n$$$ lines contains four integers $$$u_i, l_i, d_i, r_i$$$ ($$$1 \le u_i \le d_i \le 2$$$; $$$1 \le l_i \le r_i \le 10^9$$$) — the coordinates of cells located in the top-left and the bottom-right corners of the rectangle, respectively.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, first print an integer $$$s$$$ — the largest possible covered by new rectangles area. Then print $$$n$$$ lines with your solution to cover this area.In the $$$i$$$-th of these lines print four integers $$$u'_i, l'_i, d'_i, r'_i$$$. If you remove the $$$i$$$-th rectangle, print $$$u'_i = l'_i = d'_i = r'_i = 0$$$. Otherwise, these numbers denote the new coordinates of the top-left and the bottom-right corners of the $$$i$$$-th rectangle, satisfying $$$u_i \le u'_i \le d'_i \le d_i$$$; $$$l_i \le l'_i \le r'_i \le r_i$$$.If there are multiple solutions, print any.

Note: The picture in the statement illustrates the first test case.

Sample Inputs:
8
5
1 2 2 4
2 4 2 8
1 4 2 7
1 2 1 2
1 9 1 10
2
1 1 1 10
1 5 1 15
2
1 1 1 10
1 1 1 10
5
1 3 1 7
1 3 1 8
1 1 1 4
1 2 1 7
1 10 1 11
2
1 1 2 10
1 5 1 8
2
1 5 2 10
1 2 1 7
2
1 5 2 10
2 2 2 15
5
2 6 2 7
1 4 2 5
1 5 1 9
1 7 2 10
1 2 1 6

Sample Outputs:
15
1 2 2 4
2 5 2 8
1 5 1 7
0 0 0 0
1 9 1 10
15
1 1 1 10
1 11 1 15
10
1 1 1 10
0 0 0 0
10
0 0 0 0
1 8 1 8
1 1 1 4
1 5 1 7
1 10 1 11
20
1 1 2 10
0 0 0 0
15
1 5 2 10
1 2 1 4
20
1 5 1 10
2 2 2 15
16
2 6 2 6
2 4 2 5
0 0 0 0
1 7 2 10
1 2 1 6

Solution (Python):
def merge_one_row(arr_one, discarded):
    arr_one.sort(key=lambda x: x[1])
    st = []
    for (u, l, d, r, idx) in arr_one:
        if st and st[-1][3] >= r:
            discarded.append([0, 0, 0, 0, idx])
            continue
        if st and st[-1][3] >= l:
            st[-1][3] = l - 1
        st.append([u, l, d, r, idx])
    arr_one.clear()
    for x in st:
        arr_one.append(x)
    return None

def merge_one_with_both(arr_one, arr_both, arr_two, discarded):
    arr_one.sort(key=lambda x: x[1])
    arr_both.sort(key=lambda x: x[1])
    arr_one2 = []
    arr_both2 = []
    i = j = 0
    (n, m) = (len(arr_one), len(arr_both))
    while i < n and j < m:
        if arr_one[i][3] < arr_both[j][1]:
            arr_one2.append(arr_one[i])
            i += 1
            continue
        if arr_one[i][1] > arr_both[j][3]:
            arr_both2.append(arr_both[j])
            j += 1
            continue
        if arr_one[i][1] < arr_both[j][1] and arr_one[i][3] <= arr_both[j][3]:
            arr_one[i][3] = arr_both[j][1] - 1
            arr_one2.append(arr_one[i])
            i += 1
            continue
        if arr_one[i][1] <= arr_both[j][1] and arr_one[i][3] >= arr_both[j][3]:
            (u, l, d, r, idx) = arr_both[j]
            new_row = 3 - arr_one[i][0]
            arr_two.append([new_row, l, new_row, r, idx])
            j += 1
            continue
        if arr_one[i][1] >= arr_both[j][1] and arr_one[i][3] <= arr_both[j][3]:
            (u, l, d, r, idx) = arr_one[i]
            discarded.append([0, 0, 0, 0, idx])
            i += 1
            continue
        assert arr_one[i][1] >= arr_both[j][1] and arr_one[i][3] > arr_both[j][3]
        arr_one[i][1] = arr_both[j][3] + 1
        arr_both2.append(arr_both[j])
        j += 1
    while i < n:
        arr_one2.append(arr_one[i])
        i += 1
    while j < m:
        arr_both2.append(arr_both[j])
        j += 1
    arr_one.clear()
    arr_one.extend(arr_one2)
    arr_both.clear()
    arr_both.extend(arr_both2)
    return None

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        up = []
        down = []
        both = []
        for i in range(n):
            (u, l, d, r) = readIntArr()
            if u == d == 1:
                down.append([u, l, d, r, i])
            elif u == d == 2:
                up.append([u, l, d, r, i])
            else:
                both.append([u, l, d, r, i])
        discarded = []
        merge_one_row(up, discarded)
        merge_one_row(both, discarded)
        merge_one_with_both(up, both, down, discarded)
        merge_one_row(down, discarded)
        merge_one_with_both(down, both, up, discarded)
        ans = [[] for __ in range(n)]
        area = 0
        for arr in (up, down, both, discarded):
            for (u, l, d, r, idx) in arr:
                ans[idx] = (u, l, d, r)
                if u != 0:
                    area += (d - u + 1) * (r - l + 1)
        allans.append([area])
        allans.extend(ans)
    multiLineArrayOfArraysPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
def merge_one_row(arr_one, discarded):
    arr_one.sort(key=lambda x: x[1])
    st = []
    for (u, l, d, r, idx) in arr_one:
        if st and st[-1][3] >= r:
            discarded.append([0, 0, 0, 0, idx])
            continue
        if st and st[-1][3] >= l:
            st[-1][3] = l - 1
        st.append([u, l, d, r, idx])
    arr_one.clear()
    for x in st:
        arr_one.append(x)
    return None

def merge_one_with_both(arr_one, arr_both, arr_two, discarded):
    arr_one.sort(key=lambda x: x[1])
    arr_both.sort(key=lambda x: x[1])
    arr_one2 = []
    arr_both2 = []
    i = j = 0
    (n, m) = (len(arr_one), len(arr_both))
    while i < n and j < m:
        if arr_one[i][3] < arr_both[j][1]:
            arr_one2.append(arr_one[i])
            i += 1
            continue
        if arr_one[i][1] > arr_both[j][3]:
            arr_both2.append(arr_both[j])
            j += 1
            continue
        if arr_one[i][1] < arr_both[j][1] and arr_one[i][3] <= arr_both[j][3]:
            arr_one[i][3] = arr_both[j][1] - 1
            arr_one2.append(arr_one[i])
            i += 1
            continue
        if arr_one[i][1] <= arr_both[j][1] and arr_one[i][3] >= arr_both[j][3]:
            (u, l, d, r, idx) = arr_both[j]
            new_row = 3 - arr_one[i][0]
            arr_two.append([new_row, l, new_row, r, idx])
            j += 1
            continue
        if arr_one[i][1] >= arr_both[j][1] and arr_one[i][3] <= arr_both[j][3]:
            (u, l, d, r, idx) = arr_one[i]
            discarded.append([0, 0, 0, 0, idx])
            i += 1
            continue
        assert arr_one[i][1] >= arr_both[j][1] and arr_one[i][3] > arr_both[j][3]
        arr_one[i][1] = arr_both[j][3] + 1
        arr_both2.append(arr_both[j])
        j += 1
    while i < n:
        arr_one2.append(arr_one[i])
        i += 1
    while j < m:
        arr_both2.append(arr_both[j])
        j += 1
    arr_one.clear()
    arr_one.extend(arr_one2)
    arr_both.clear()
    arr_both.extend(arr_both2)
    return None

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        up = []
        down = []
        both = []
        for i in range(n):
            (u, l, d, r) = readIntArr()
            if u == d == 1:
                down.append([u, l, d, r, i])
            elif u == d == 2:
                up.append([u, l, d, r, i])
            else:
                both.append([u, l, d, r, i])
        discarded = []
        merge_one_row(up, discarded)
        merge_one_row(both, discarded)
        merge_one_with_both(up, both, down, discarded)
        merge_one_row(down, discarded)
        merge_one_with_both(down, both, up, discarded)
        ans = [[] for __ in range(n)]
        area = 0
        for arr in (up, down, both, discarded):
            for (u, l, d, r, idx) in arr:
                ans[idx] = (u, l, d, r)
                if u != 0:
                    area += (d - u + 1) * (r - l + 1)
        allans.append([area])
        allans.extend(ans)
    multiLineArrayOfArraysPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * inf + inf - v
t = int(input())
ans = []
inf = pow(10, 9) + 1
for _ in range(t):
    n = int(input())
    (a, b, c) = ([], [], [])
    for i in range(n):
        (u, l, d, r) = map(int, input().split())
        if d == 1:
            a.append((f(l, r), i))
        elif u == 2:
            b.append((f(l, r), i))
        else:
            c.append((f(l, r), i))
    c.sort()
    (l, r) = ([inf] * n, [-inf] * n)
    (u, d) = ([inf] * n, [-inf] * n)
    x = []
    ma = 0
    for (i, j) in c:
        (l0, r0) = divmod(i, inf)
        r0 = inf - r0
        if r0 <= ma:
            continue
        (u[j], d[j]) = (1, 2)
        ma = max(ma, r0)
        (l[j], r[j]) = (l0, r0)
        x.append(j)
    for i in range(len(x) - 1):
        (j, k) = (x[i], x[i + 1])
        r[j] = min(l[k] - 1, r[j])
    (l0, r0) = (inf, -inf)
    (y, y0) = ([], [])
    (l1, r1) = ([], [])
    for i in x:
        if l0 == inf:
            y0.append(i)
            (l0, r0) = (l[i], r[i])
        elif r0 + 1 == l[i]:
            y0.append(i)
            r0 = r[i]
        else:
            a.append((f(l0, r0), len(l)))
            b.append((f(l0, r0), len(l)))
            y.append(list(y0))
            y0 = [i]
            l.append(l0)
            r.append(r0)
            (l0, r0) = (l[i], r[i])
    if l0 ^ inf:
        a.append((f(l0, r0), len(l)))
        b.append((f(l0, r0), len(l)))
        y.append(list(y0))
        l.append(l0)
        r.append(r0)
    a.sort()
    b.sort()
    ma = 0
    x = []
    for (i, j) in a:
        (l0, r0) = divmod(i, inf)
        r0 = inf - r0
        if r0 <= ma:
            if j >= n:
                for k in y[j - n]:
                    u[k] = 2
            continue
        if j < n:
            (l[j], r[j]) = (l0, r0)
            (u[j], d[j]) = (1, 1)
        ma = max(ma, r0)
        x.append(j)
    (ngl, ngr) = (inf, -inf)
    for i in range(len(x)):
        j = x[i]
        if j >= n:
            (ngl, ngr) = (l[j], r[j])
        else:
            l[j] = max(l[j], ngr + 1)
    (ngl, ngr) = (inf, -inf)
    for i in range(len(x) - 1, -1, -1):
        j = x[i]
        if j >= n:
            (ngl, ngr) = (l[j], r[j])
        else:
            r[j] = min(r[j], ngl - 1)
    for i in range(len(x) - 1):
        (j, k) = (x[i], x[i + 1])
        if r[j] < l[k]:
            continue
        if j >= n:
            l[k] = r[j] + 1
        else:
            r[j] = l[k] - 1
    ma = 0
    x = []
    for (i, j) in b:
        (l0, r0) = divmod(i, inf)
        r0 = inf - r0
        if r0 <= ma:
            if j >= n:
                for k in y[j - n]:
                    d[k] = 1
            continue
        if j < n:
            (l[j], r[j]) = (l0, r0)
            (u[j], d[j]) = (2, 2)
        ma = max(ma, r0)
        x.append(j)
    (ngl, ngr) = (inf, -inf)
    for i in range(len(x)):
        j = x[i]
        if j >= n:
            (ngl, ngr) = (l[j], r[j])
        else:
            l[j] = max(l[j], ngr + 1)
    (ngl, ngr) = (inf, -inf)
    for i in range(len(x) - 1, -1, -1):
        j = x[i]
        if j >= n:
            (ngl, ngr) = (l[j], r[j])
        else:
            r[j] = min(r[j], ngl - 1)
    for i in range(len(x) - 1):
        (j, k) = (x[i], x[i + 1])
        if r[j] < l[k]:
            continue
        if j >= n:
            l[k] = r[j] + 1
        else:
            r[j] = l[k] - 1
    s = 0
    ans0 = []
    for i in range(n):
        (ui, li, di, ri) = (u[i], l[i], d[i], r[i])
        if ui > di or li > ri:
            ans0.append('0 0 0 0')
        else:
            s += (di - ui + 1) * (ri - li + 1)
            ans0.append(' '.join(map(str, (ui, li, di, ri))))
    ans.append(str(s))
    ans.append('\n'.join(ans0))
sys.stdout.write('\n'.join(ans))