Choose a Square (Codeforces 1221F)
Tags: Others, binary search

Petya recently found a game "Choose a Square". In this game, there are $$$n$$$ points numbered from $$$1$$$ to $$$n$$$ on an infinite field. The $$$i$$$-th point has coordinates $$$(x_i, y_i)$$$ and cost $$$c_i$$$.You have to choose a square such that its sides are parallel to coordinate axes, the lower left and upper right corners belong to the line $$$y = x$$$, and all corners have integer coordinates.The score you get is the sum of costs of the points covered by the selected square minus the length of the side of the square. Note that the length of the side can be zero.Petya asks you to calculate the maximum possible score in the game that can be achieved by placing exactly one square.

Input: The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the number of points on the field.Each of the following $$$n$$$ lines contains three integers $$$x_i, y_i, c_i$$$ ($$$0 \le x_i, y_i \le 10^9, -10^6 \le c_i \le 10^6$$$) — coordinates of the $$$i$$$-th point and its cost, respectively.

Output: In the first line print the maximum score Petya can achieve.In the second line print four integers $$$x_1, y_1, x_2, y_2$$$ ($$$0 \le x_1, y_1, x_2, y_2 \le 2 \cdot 10^9, x_1 = y_1, x_2 = y_2, x_1 \le x_2$$$) separated by spaces — the coordinates of the lower left and upper right corners of the square which Petya has to select in order to achieve the maximum score.

Note: The field corresponding to the first example: 

Sample Inputs:
6
0 0 2
1 0 -5
1 1 3
2 3 4
1 4 -4
3 1 -1

5
3 3 0
3 3 -3
0 2 -1
3 1 3
0 0 -2

Sample Outputs:
4
1 1 3 3

0
1 1 1 1

Solution (Python):
(standard_input, packages, output_together) = (1, 1, 0)
(dfs, hashing, read_from_file) = (1, 0, 0)
de = 1
if 1:
    if standard_input:
        import io, os, sys
        input = lambda : sys.stdin.readline().rstrip()
        import math
        inf = math.inf

        def I():
            return input()

        def II():
            return int(input())

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

        def LI():
            return list(input().split())

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

        def LFI():
            return list(map(float, input().split()))

        def GMI():
            return map(lambda x: int(x) - 1, input().split())

        def LGMI():
            return list(map(lambda x: int(x) - 1, input().split()))
    if packages:
        from io import BytesIO, IOBase
        import random
        import os
        import bisect
        import typing
        from collections import Counter, defaultdict, deque
        from copy import deepcopy
        from functools import cmp_to_key, lru_cache, reduce
        from heapq import merge, heapify, heappop, heappush, heappushpop, nlargest, nsmallest
        from itertools import accumulate, combinations, permutations, count, product
        from operator import add, iand, ior, itemgetter, mul, xor
        from string import ascii_lowercase, ascii_uppercase, ascii_letters
        from typing import *
        BUFSIZE = 4096
    if output_together:

        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.stdout = IOWrapper(sys.stdout)
    if dfs:
        from types import GeneratorType

        def bootstrap(f, stack=[]):

            def wrappedfunc(*args, **kwargs):
                if stack:
                    return f(*args, **kwargs)
                else:
                    to = f(*args, **kwargs)
                    while True:
                        if type(to) is GeneratorType:
                            stack.append(to)
                            to = next(to)
                        else:
                            stack.pop()
                            if not stack:
                                break
                            to = stack[-1].send(to)
                    return to
            return wrappedfunc
    if hashing:
        RANDOM = random.getrandbits(20)

        class Wrapper(int):

            def __init__(self, x):
                int.__init__(x)

            def __hash__(self):
                return super(Wrapper, self).__hash__() ^ RANDOM
    if read_from_file:
        file = open('input.txt', 'r').readline().strip()[1:-1]
        fin = open(file, 'r')
        input = lambda : fin.readline().strip()
        output_file = open('output.txt', 'w')

        def fprint(*args, **kwargs):
            print(*args, **kwargs, file=output_file)
    if de:

        def debug(*args, **kwargs):
            print('\x1b[92m', end='')
            print(*args, **kwargs)
            print('\x1b[0m', end='')

class SegTree:

    def __init__(self, v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._n = len(v)
        self._log = (self._n - 1).bit_length()
        self._size = 1 << self._log
        self._d = [0] * (2 * self._size)
        self._tot = [0] * (2 * self._size)
        self._max_idx = [-1] * (2 * self._size)
        for i in range(self._n):
            self._d[self._size + i] = v[i]
            self._tot[self._size + i] = v[i]
            self._max_idx[self._size + i] = i
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n
        p += self._size
        self._d[p] += x
        self._tot[p] += x
        for i in range(1, self._log + 1):
            self._update(p >> i)

    def all_prod(self) -> typing.Any:
        return (self._d[1], self._max_idx[1])

    def _update(self, k: int) -> None:
        self._tot[k] = self._tot[k * 2] + self._tot[k * 2 + 1]
        if self._d[k * 2] >= self._tot[k * 2] + self._d[k * 2 + 1]:
            self._d[k] = self._d[k * 2]
            self._max_idx[k] = self._max_idx[k * 2]
        else:
            self._d[k] = self._tot[k * 2] + self._d[k * 2 + 1]
            self._max_idx[k] = self._max_idx[k * 2 + 1]
n = II()
xs = []
ys = []
cs = []
for _ in range(n):
    (x, y, c) = MII()
    if x > y:
        (x, y) = (y, x)
    xs.append(x)
    ys.append(y)
    cs.append(c)
pts = sorted(set(sorted(xs + ys)))
d = {v: i for (i, v) in enumerate(pts)}
m = len(pts)
vals = [0] * m
for i in range(1, m):
    vals[i] = -(pts[i] - pts[i - 1])
lefts = [[] for _ in range(m)]
for i in range(n):
    lefts[d[xs[i]]].append(i)
    vals[d[ys[i]]] += cs[i]
seg = SegTree(vals)
ans = 0
l = r = 2 * 10 ** 9
for i in range(m):
    if i:
        seg.set(i, pts[i] - pts[i - 1])
    (v, idx) = seg.all_prod()
    if v > ans:
        ans = v
        l = pts[i]
        r = pts[idx]
    for pt in lefts[i]:
        seg.set(d[ys[pt]], -cs[pt])
print(ans)
print(l, l, r, r)

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]

class lazy_segtree:

    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def push(self, k):
        self.all_apply(2 * k, self.lz[k])
        self.all_apply(2 * k + 1, self.lz[k])
        self.lz[k] = self.identity

    def __init__(self, V, OP, E, MAPPING, COMPOSITION, ID):
        self.n = len(V)
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [E for i in range(2 * self.size)]
        self.lz = [ID for i in range(self.size)]
        self.e = E
        self.op = OP
        self.mapping = MAPPING
        self.composition = COMPOSITION
        self.identity = ID
        for i in range(self.n):
            self.d[self.size + i] = V[i]
        for i in range(self.size - 1, 0, -1):
            self.update(i)

    def set(self, p, x):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def get(self, p):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        assert 0 <= l and l <= r and (r <= self.n)
        if l == r:
            return self.e
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if l >> i << i != l:
                self.push(l >> i)
            if r >> i << i != r:
                self.push(r >> i)
        (sml, smr) = (self.e, self.e)
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.d[1]

    def apply_point(self, p, f):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = self.mapping(f, self.d[p])
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def apply(self, l, r, f):
        assert 0 <= l and l <= r and (r <= self.n)
        if l == r:
            return
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if l >> i << i != l:
                self.push(l >> i)
            if r >> i << i != r:
                self.push(r - 1 >> i)
        (l2, r2) = (l, r)
        while l < r:
            if l & 1:
                self.all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.all_apply(r, f)
            l >>= 1
            r >>= 1
        (l, r) = (l2, r2)
        for i in range(1, self.log + 1):
            if l >> i << i != l:
                self.update(l >> i)
            if r >> i << i != r:
                self.update(r - 1 >> i)

    def max_right(self, l, g):
        assert 0 <= l and l <= self.n
        assert g(self.e)
        if l == self.n:
            return self.n
        l += self.size
        for i in range(self.log, 0, -1):
            self.push(l >> i)
        sm = self.e
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not g(self.op(sm, self.d[l])):
                while l < self.size:
                    self.push(l)
                    l = 2 * l
                    if g(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if l & -l == l:
                break
        return self.n

    def min_left(self, r, g):
        assert 0 <= r and r <= self.n
        assert g(self.e)
        if r == 0:
            return 0
        r += self.size
        for i in range(self.log, 0, -1):
            self.push(r - 1 >> i)
        sm = self.e
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not g(self.op(self.d[r], sm)):
                while r < self.size:
                    self.push(r)
                    r = 2 * r + 1
                    if g(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if r & -r == r:
                break
        return 0
from collections import defaultdict
s = []
n = int(input())
points = []
for _ in range(n):
    (x, y, c) = map(int, input().split())
    if x > y:
        (x, y) = (y, x)
    points.append((x, y, c))
    s.append(x)
    s.append(y)
s.sort()
t = [s[0]]
for i in s[1:]:
    if t[-1] != i:
        t.append(i)
s = t
m = len(s)
import bisect
LR = [[] for i in range(m)]
for (l, r, c) in points:
    L = bisect.bisect_left(s, l)
    R = bisect.bisect_left(s, r)
    LR[L].append((R, c))

def ope(L, R):
    return max(L, R)

def mapping(f, x):
    (x0, x1) = int_to_tup(x)
    return tup_to_int(x0 + f, x1)

def composition(f, g):
    return f + g

def tup_to_int(x, y):
    return (x << 20) + y
mask = (1 << 20) - 1

def int_to_tup(x):
    x0 = x >> 20
    x1 = x & mask
    return (x0, x1)
inf = 10 ** 12
seg = lazy_segtree([tup_to_int(-s[i] + inf, i) for i in range(m)], ope, m, mapping, composition, 0)
(ans, ansL, ansR) = (inf, 2 * 10 ** 9, 2 * 10 ** 9)
for L in range(m - 1, -1, -1):
    if LR[L]:
        for (R, c) in LR[L]:
            seg.apply(R, m, c)
        res = seg.prod(L, m)
        (res0, res1) = int_to_tup(res)
        if ans < res0 + s[L] and res1 != m:
            ans = res0 + s[L]
            ansL = s[L]
            ansR = s[res1]
print(ans - inf)
print(ansL, ansL, ansR, ansR)

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

def update(l, r, s):
    (q, ll, rr, i) = ([1], [0], [l1 - 1], 0)
    while len(q) ^ i:
        j = q[i]
        (l0, r0) = (ll[i], rr[i])
        if l <= l0 and r0 <= r:
            lazy[j] += s
            i += 1
            continue
        m0 = l0 + r0 >> 1
        if j < l1:
            lazy[2 * j] += lazy[j]
            lazy[2 * j + 1] += lazy[j]
            lazy[j] = 0
        if l <= m0 and l0 <= r:
            q.append(2 * j)
            ll.append(l0)
            rr.append(m0)
        if l <= r0 and m0 + 1 <= r:
            q.append(2 * j + 1)
            ll.append(m0 + 1)
            rr.append(r0)
        i += 1
    for i in reversed(q):
        if i < l1:
            tree[i] = max(tree[2 * i] + lazy[2 * i], tree[2 * i + 1] + lazy[2 * i + 1])
    return

def get_max(s, t):
    update(s, t, 0)
    s += l1
    t += l1
    ans = inf
    while s <= t:
        if s % 2:
            ans = max(ans, tree[s] + lazy[s])
            s += 1
        s >>= 1
        if not t % 2:
            ans = max(ans, tree[t] + lazy[t])
            t -= 1
        t >>= 1
    return ans
n = int(input())
u = defaultdict(lambda : [])
v = defaultdict(lambda : [])
c = [0]
for i in range(n):
    (x, y, c0) = map(int, input().split())
    if x > y:
        (x, y) = (y, x)
    u[x].append(i + 1)
    v[y].append(i + 1)
    c.append(c0)
u0 = [0] + list(sorted(u.keys()))
v0 = [0] + list(sorted(v.keys()))
l = len(v0)
a = [0] * l
b = [0] * (n + 1)
la = u0[1]
for i in range(1, l):
    a[i] -= v0[i] - la
    for j in v[v0[i]]:
        a[i] += c[j]
        b[j] = i
    la = v0[i]
for i in range(1, l):
    a[i] += a[i - 1]
for i in range(1, l):
    a[i] *= l + 1
    a[i] += i
inf = -pow(10, 17) - 1
l1 = pow(2, l.bit_length())
l2 = 2 * l1
(tree, lazy) = ([0] * l2, [0] * l2)
for i in range(len(a)):
    tree[i + l1] = a[i]
for i in range(l1 - 1, 0, -1):
    tree[i] = max(tree[2 * i], tree[2 * i + 1])
la = u0[1]
c0 = 0
j = 1
ans = 0
xy = []
for i in range(1, len(u0)):
    while j < l and v0[j] < u0[i]:
        j += 1
    c0 += u0[i] - la
    la = u0[i]
    x = get_max(j, l - 1)
    ans0 = x // (l + 1) + c0
    if ans < ans0:
        ans = ans0
        z = x % (l + 1)
        xy = [u0[i], u0[i], v0[z], v0[z]]
    for k in u[u0[i]]:
        update(b[k], l, -c[k] * (l + 1))
if not len(xy):
    z = pow(10, 9) + 1
    xy = [z] * 4
print(ans)
sys.stdout.write(' '.join(map(str, xy)))