Boring Segments (Codeforces 1555E)
Tags: Others, trees

You are given $$$n$$$ segments on a number line, numbered from $$$1$$$ to $$$n$$$. The $$$i$$$-th segments covers all integer points from $$$l_i$$$ to $$$r_i$$$ and has a value $$$w_i$$$.You are asked to select a subset of these segments (possibly, all of them). Once the subset is selected, it's possible to travel between two integer points if there exists a selected segment that covers both of them. A subset is good if it's possible to reach point $$$m$$$ starting from point $$$1$$$ in arbitrary number of moves.The cost of the subset is the difference between the maximum and the minimum values of segments in it. Find the minimum cost of a good subset.In every test there exists at least one good subset.

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$2 \le m \le 10^6$$$) — the number of segments and the number of integer points.Each of the next $$$n$$$ lines contains three integers $$$l_i$$$, $$$r_i$$$ and $$$w_i$$$ ($$$1 \le l_i < r_i \le m$$$; $$$1 \le w_i \le 10^6$$$) — the description of the $$$i$$$-th segment.In every test there exists at least one good subset.

Output: Print a single integer — the minimum cost of a good subset.


Sample Inputs:
5 12
1 5 5
3 4 10
4 10 6
11 12 5
10 12 3

1 10
1 10 23

Sample Outputs:
3

0

Solution (Python):
import os, sys
from io import BytesIO, IOBase
inf = float('inf')

def build(tree, lazy, pos):
    pos >>= 1
    while pos:
        tree[pos] = min(tree[pos << 1], tree[pos << 1 | 1]) + lazy[pos]
        pos >>= 1

def apply(tree, lazy, pos, val):
    tree[pos] += val
    if pos < len(lazy):
        lazy[pos] += val

def push(tree, lazy, pos, h):
    for s in range(h, 0, -1):
        ne = pos >> s
        if lazy[ne]:
            apply(tree, lazy, ne << 1, lazy[ne])
            apply(tree, lazy, ne << 1 | 1, lazy[ne])
            lazy[ne] = 0

def update(tree, lazy, l, r, val, si):
    (l, r) = (l + si - 1, r + si - 1)
    (l0, r0) = (l, r)
    while l < r:
        if l & 1:
            apply(tree, lazy, l, val)
            l += 1
        if not r & 1:
            apply(tree, lazy, r, val)
            r -= 1
        (l, r) = (l >> 1, r >> 1)
    if l == r:
        apply(tree, lazy, l, val)
    build(tree, lazy, l0)
    build(tree, lazy, r0)

def query(tree, lazy, l, r, si, h):
    (l, r, ans) = (l + si - 1, r + si - 1, inf)
    push(tree, lazy, l, h)
    push(tree, lazy, r, h)
    while l < r:
        if l & 1:
            ans = min(ans, tree[l])
            l += 1
        if not r & 1:
            ans = min(ans, tree[r])
            r -= 1
        (l, r) = (l >> 1, r >> 1)
    if l == r:
        return min(ans, tree[l])
    return ans

def main():
    (n, m) = map(int, input().split())
    m <<= 1
    h = m.bit_length() - (not m & m - 1)
    si = 1 << h
    tree = [0] * (si << 1)
    lazy = [0] * (si << 1)
    (l, r, w) = ([], [], [])
    for _ in range(n):
        (l1, r1, w1) = map(int, input().split())
        l.append(2 * l1)
        r.append(2 * r1)
        w.append(w1)
    rr = sorted(range(n), key=lambda xx: w[xx])
    (j, ans) = (0, inf)
    for (idx, i) in enumerate(rr):
        (st, en) = (l[i], r[i])
        update(tree, lazy, st, en, 1, si)
        while query(tree, lazy, 2, m, si, h):
            ans = min(ans, w[i] - w[rr[j]])
            update(tree, lazy, l[rr[j]], r[rr[j]], -1, si)
            j += 1
    print(ans)
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')
if __name__ == '__main__':
    main()

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

def make_tree(n):
    n0 = 1
    while n0 < n:
        n0 *= 2
    tree = [inf] * (2 * n0)
    lazy = [inf] * (2 * n0)
    return (tree, lazy)

def eval(s, t, a):
    b = []
    (u, v) = ([0, len(tree) // 2 - 1], [0, len(tree) // 2 - 1])
    (x, y) = (1, 1)
    if lazy[x] ^ inf:
        tree[x] = lazy[x]
    while u[0] ^ u[1]:
        (lx, ly) = (lazy[x], lazy[y])
        if not x in a:
            b.append(x)
        if lx ^ inf:
            lazy[x] = inf
            (lazy[2 * x], lazy[2 * x + 1]) = (lx, lx)
            (tree[2 * x], tree[2 * x + 1]) = (lx, lx)
        if not y in a:
            b.append(y)
        if ly ^ inf:
            lazy[y] = inf
            (lazy[2 * y], lazy[2 * y + 1]) = (ly, ly)
            (tree[2 * y], tree[2 * y + 1]) = (ly, ly)
        (u0, u1) = u
        if u0 <= s <= (u0 + u1) // 2:
            u1 = (u0 + u1) // 2
            x = 2 * x
        else:
            u0 = (u0 + u1) // 2 + 1
            x = 2 * x + 1
        u = [u0, u1]
        (v0, v1) = v
        if v0 <= t <= (v0 + v1) // 2:
            v1 = (v0 + v1) // 2
            y = 2 * y
        else:
            v0 = (v0 + v1) // 2 + 1
            y = 2 * y + 1
        v = [v0, v1]
    (tree[x], tree[y]) = (lazy[x], lazy[y])
    return b

def update(s, t, x):
    (s0, t0) = (s, t)
    s += len(tree) // 2
    t += len(tree) // 2
    a = set()
    while s <= t:
        if s % 2 == 0:
            s //= 2
        else:
            a.add(s)
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            a.add(t)
            t = (t - 1) // 2
    b = eval(s0, t0, a)
    for i in a:
        (tree[i], lazy[i]) = (x, x)
    while b:
        i = b.pop()
        tree[i] = min(tree[2 * i], tree[2 * i + 1])
    return

def get_min(s, t):
    (s0, t0) = (s, t)
    s += len(tree) // 2
    t += len(tree) // 2
    a = set()
    while s <= t:
        if s % 2 == 0:
            s //= 2
        else:
            a.add(s)
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            a.add(t)
            t = (t - 1) // 2
    eval(s0, t0, a)
    ans = n1
    for i in a:
        ans = min(ans, tree[i])
    return ans
(n, m) = map(int, input().split())
n1 = pow(10, 6) + 5
inf = -n1
(tree, lazy) = make_tree(m + 5)
x = [[] for _ in range(n1)]
for _ in range(n):
    (l, r, w) = map(int, input().split())
    x[w].append((l, r - 1))
ans = n1
for w1 in range(1, n1):
    if not x[w1]:
        continue
    for (l0, r0) in x[w1]:
        update(l0, r0, w1)
    w0 = get_min(1, m - 1)
    ans = min(ans, w1 - w0)
print(ans)

Solution (Python):
import os
import sys
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')

class LazySegmentTree:

    def __init__(self, data, default=0, func=min):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self._lazy = [0] * (2 * _size)
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __len__(self):
        return self._len

    def _push(self, idx):
        """"""
        (q, self._lazy[idx]) = (self._lazy[idx], 0)
        self._lazy[2 * idx] += q
        self._lazy[2 * idx + 1] += q
        self.data[2 * idx] += q
        self.data[2 * idx + 1] += q

    def _update(self, idx):
        """"""
        for i in reversed(range(1, idx.bit_length())):
            self._push(idx >> i)

    def _build(self, idx):
        """"""
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1]) + self._lazy[idx]
            idx >>= 1

    def add(self, start, stop, value):
        """"""
        start = start_copy = start + self._size
        stop = stop_copy = stop + self._size
        while start < stop:
            if start & 1:
                self._lazy[start] += value
                self.data[start] += value
                start += 1
            if stop & 1:
                stop -= 1
                self._lazy[stop] += value
                self.data[stop] += value
            start >>= 1
            stop >>= 1
        self._build(start_copy)
        self._build(stop_copy - 1)

    def query(self, start, stop, default=1000000000.0):
        """"""
        start += self._size
        stop += self._size
        self._update(start)
        self._update(stop - 1)
        res = default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return 'LazySegmentTree({0})'.format(self.data)
(n, m) = map(int, input().split())
t = LazySegmentTree(data=[0] * (m + 5))
I = [None] * n
for i in range(n):
    (l, r, w) = map(int, input().split())
    I[i] = (l, r, w)
I.sort(key=lambda p: p[2])
(i, j) = (0, 0)
ans = 1 << 32
while i < n:
    if i >= 1:
        t.add(I[i - 1][0], I[i - 1][1], -1)
    while j < n and (not t.query(1, m)):
        t.add(I[j][0], I[j][1], 1)
        j += 1
    if t.query(1, m):
        ans = min(ans, I[j - 1][2] - I[i][2])
    i += 1
print(ans)