Tenzing and Triangle (Codeforces 1842E)
Tags: Math, geometry

There are $$$n$$$ pairwise-distinct points and a line $$$x+y=k$$$ on a two-dimensional plane. The $$$i$$$-th point is at $$$(x_i,y_i)$$$. All points have non-negative coordinates and are strictly below the line. Alternatively, $$$0 \leq x_i,y_i, x_i+y_i < k$$$.Tenzing wants to erase all the points. He can perform the following two operations:  Draw triangle: Tenzing will choose two non-negative integers $$$a$$$, $$$b$$$ that satisfy $$$a+b<k$$$, then all points inside the triangle formed by lines $$$x=a$$$, $$$y=b$$$ and $$$x+y=k$$$ will be erased. It can be shown that this triangle is an isosceles right triangle. Let the side lengths of the triangle be $$$l$$$, $$$l$$$ and $$$\sqrt 2 l$$$ respectively. Then, the cost of this operation is $$$l \cdot A$$$.The blue area of the following picture describes the triangle with $$$a=1,b=1$$$ with cost $$$=1\cdot A$$$.   Erase a specific point: Tenzing will choose an integer $$$i$$$ that satisfies $$$1 \leq i \leq n$$$ and erase the point $$$i$$$. The cost of this operation is $$$c_i$$$.Help Tenzing find the minimum cost to erase all of the points.

Input: The first line of the input contains three integers $$$n$$$, $$$k$$$ and $$$A$$$ ($$$1\leq n,k\leq 2\cdot 10^5$$$, $$$1\leq A\leq 10^4$$$) — the number of points, the coefficient describing the hypotenuse of the triangle and the coefficient describing the cost of drawing a triangle.The following $$$n$$$ lines of the input the $$$i$$$-th line contains three integers $$$x_i,y_i,c_i$$$ ($$$0\leq x_i,y_i,x_i+y_i< k$$$, $$$1\leq c_i\leq 10^4$$$) — the coordinate of the $$$i$$$-th points and the cost of erasing it using the second operation. It is guaranteed that the coordinates are pairwise distinct.

Output: Output a single integer —the minimum cost needed to erase all of the points.

Note: The picture of the first example:Tenzing do the following operations: draw a triangle with $$$a=3,b=2$$$, the cost $$$=1\cdot A=1$$$.  erase the first point, the cost $$$=1$$$.  erase the second point, the cost $$$=1$$$.  erase the third point, the cost $$$=1$$$.  The picture of the second example:   

Sample Inputs:
4 6 1
1 2 1
2 1 1
1 1 1
3 2 6

6 7 1
4 2 1
3 3 1
5 1 4
3 2 5
4 1 1
0 6 4

10 4 100
0 0 1
0 1 1
0 2 50
0 3 200
1 0 1
1 1 1
1 2 1
2 0 200
2 1 200
3 0 200

Sample Outputs:
4

4

355

Solution (Python):
import os, sys, collections, heapq, itertools, functools, operator, random
if os.path.exists('in.txt'):
    file = open('in.txt')
    input = file.readline
else:
    input = sys.stdin.readline
from functools import reduce, lru_cache
from itertools import accumulate, chain, combinations, count
from itertools import groupby, permutations, product, zip_longest
from heapq import heapify, heappush, heappop, heapreplace, merge, nlargest, nsmallest
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect_right
from math import comb, floor, ceil, inf, gcd, sqrt, atan2
from copy import copy
from random import randint
readi = lambda : int(input())
readis = lambda : list(map(int, input().split()))
reads = lambda : input().rstrip()
readss = lambda : input().split()

class SEGMENTTREE_ADD_MAX:

    def __init__(self, n=10 ** 9, q=10 ** 5):
        self.N = 1 << (n + 2).bit_length()
        self.A = defaultdict(int) if n > q * n.bit_length() else [0] * (self.N * 2)

    def update(self, l, r, x):
        (A, N) = (self.A, self.N)
        if l <= 0:
            r += N + 1
            while r > 1:
                if r & 1:
                    A[r ^ 1] += x
                tmp = max(A[r], A[r ^ 1])
                A[r] -= tmp
                A[r ^ 1] -= tmp
                A[r >> 1] += tmp
                r >>= 1
        elif r >= N - 1:
            l += N - 1
            while l > 1:
                if ~l & 1:
                    A[l ^ 1] += x
                tmp = max(A[l], A[l ^ 1])
                A[l] -= tmp
                A[l ^ 1] -= tmp
                A[l >> 1] += tmp
                l >>= 1
        elif l == r:
            (A, N) = (self.A, self.N)
            l += N
            A[l] += x
            while l > 1:
                tmp = max(A[l], A[l ^ 1])
                A[l] -= tmp
                A[l ^ 1] -= tmp
                A[l >> 1] += tmp
                l >>= 1
        elif l < r:
            l += N - 1
            r += N + 1
            while l ^ r ^ 1:
                if ~l & 1:
                    A[l ^ 1] += x
                if r & 1:
                    A[r ^ 1] += x
                tmp = max(A[l], A[l ^ 1])
                A[l] -= tmp
                A[l ^ 1] -= tmp
                A[l >> 1] += tmp
                tmp = max(A[r], A[r ^ 1])
                A[r] -= tmp
                A[r ^ 1] -= tmp
                A[r >> 1] += tmp
                l >>= 1
                r >>= 1
            while l > 1:
                tmp = max(A[l], A[l ^ 1])
                A[l] -= tmp
                A[l ^ 1] -= tmp
                A[l >> 1] += tmp
                l >>= 1

    def query(self, l, r):
        (A, N) = (self.A, self.N)
        l += N
        r += N
        S = T = 0
        if l ^ r:
            while l ^ r ^ 1:
                S += A[l]
                T += A[r]
                if ~l & 1:
                    S = max(S, A[l ^ 1])
                if r & 1:
                    T = max(T, A[r ^ 1])
                l >>= 1
                r >>= 1
        S = max(A[l] + S, A[r] + T)
        while l > 1:
            l >>= 1
            S += A[l]
        return S

def solution():
    (n, k, A) = readis()
    t = SEGMENTTREE_ADD_MAX(k, n)
    E = [[] for _ in range(k + 1)]
    s = 0
    for _ in range(n):
        (a, b, c) = readis()
        E[k - b].append([a, c])
        s += c
    dp = 0
    for r in range(k + 1):
        for (l, c) in E[r]:
            t.update(0, l, c)
        dp = max(dp, t.A[1] - A * r)
        t.update(r, r, dp + r * A)
    print(s - dp)
for i in range(1 if 1 else readi()):
    solution()

Solution (Python):
import collections, math, bisect, heapq, random, functools, itertools, copy, typing
import platform
LOCAL = platform.uname().node == 'AMO'
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda f=int: list(map(f, input().split()))

def make_arr(*args):

    def func(x):
        if len(args) == 1:
            return [x() for _ in range(args[0])]
        return [make_arr(*args[1:])(x) for _ in range(args[0])]
    return func

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

def printf(*args):
    if LOCAL:
        print('>>>: ', end='')
    for arg in args:
        if isinstance(arg, typing.Iterable) and (not isinstance(arg, str)) and (not isinstance(arg, dict)):
            print(' '.join(map(str, arg)), end=' ')
        else:
            print(arg, end=' ')
    print()

class UnionFind:

    def __init__(self, x) -> None:
        self.uf = [-1] * x

    def find(self, x):
        r = x
        while self.uf[x] >= 0:
            x = self.uf[x]
        while r != x:
            (self.uf[r], r) = (x, self.uf[r])
        return x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def merge(self, x, y):
        (ux, uy) = (self.find(x), self.find(y))
        self.uf[ux] += self.uf[uy]
        self.uf[uy] = ux
        return True

    def union(self, x, y):
        (ux, uy) = (self.find(x), self.find(y))
        if ux == uy:
            return False
        if self.uf[ux] >= self.uf[uy]:
            self.uf[uy] += self.uf[ux]
            self.uf[ux] = uy
        else:
            self.uf[ux] += self.uf[uy]
            self.uf[uy] = ux
        return True

    def count(self):
        return sum((f < 0 for f in self.uf))

    def valid(self):
        n = len(self.uf)
        for c in range(n):
            if self.uf[c] == -n:
                return True
        return False

    def roots(self):
        return [i for (i, f) in enumerate(self.uf) if f < 0]

    def groups(self):
        n = len(self.uf)
        ret = [[] for _ in range(n)]
        for i in range(n):
            f = self.find(i)
            ret[f].append(i)
        return ret

    def __print__(self):
        return self.uf

class Encodict:

    def __init__(self, func=lambda : 0):
        self.RANDOM = random.randint(0, 1 << 32)
        self.default = func
        self.dict = {}

    def __getitem__(self, key):
        k = self.RANDOM ^ key
        if k not in self.dict:
            self.dict[k] = self.default()
        return self.dict[k]

    def __setitem__(self, key, item):
        k = self.RANDOM ^ key
        self.dict[k] = item

    def keys(self):
        return [self.RANDOM ^ i for i in self.dict]

    def items(self):
        return [(self.RANDOM ^ i, self.dict[i]) for i in self.dict]

    def sorted(self, by_value=False, reverse=False):
        if by_value:
            self.dict = dict(sorted(self.dict.items(), key=lambda x: x[1], reverse=reverse))
        else:
            self.dict = dict(sorted(self.dict.items(), key=lambda x: self.RANDOM ^ x[0], reverse=reverse))

def solve(cas):
    (n, k, a) = inp()
    mp = Encodict(list)
    for i in range(n):
        (x, y, c) = inp()
        mp[k - x - 1].append((y, c))
    uf = UnionFind(k + 1)
    cap = make_arr(k)(lambda : a)
    res = 0
    for r in range(k):
        for (l, c) in mp[r]:
            i = uf.find(l)
            while i <= r and c > 0:
                tmp = min(c, cap[i])
                res += tmp
                cap[i] -= tmp
                c -= tmp
                if cap[i] == 0:
                    uf.merge(i + 1, i)
                i = uf.find(i)
    print(res)
cas = 1
for _ in range(cas):
    solve(_)

Solution (Python):
import os, sys, collections, heapq, itertools, functools, operator, random
if os.path.exists('in.txt'):
    file = open('in.txt')
    input = file.readline
else:
    input = sys.stdin.readline
from functools import reduce, lru_cache
from itertools import accumulate, chain, combinations, count
from itertools import groupby, permutations, product, zip_longest
from heapq import heapify, heappush, heappop, heapreplace, merge, nlargest, nsmallest
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect_right
from math import comb, floor, ceil, inf, gcd, sqrt, atan2
from copy import copy
from random import randint
readi = lambda : int(input())
readis = lambda : list(map(int, input().split()))
reads = lambda : input().rstrip()
readss = lambda : input().split()

class SEGMENTTREE_ADD_MAX:

    def __init__(self, n=10 ** 9, q=10 ** 5):
        self.N = 1 << (n + 2).bit_length()
        self.A = defaultdict(int) if n > q * n.bit_length() else [0] * (self.N * 2)

    def update(self, l, r, x):
        (A, N) = (self.A, self.N)
        if l <= 0:
            r += N + 1
            while r > 1:
                if r & 1:
                    A[r ^ 1] += x
                tmp = max(A[r], A[r ^ 1])
                A[r] -= tmp
                A[r ^ 1] -= tmp
                A[r >> 1] += tmp
                r >>= 1
        elif r >= N - 1:
            l += N - 1
            while l > 1:
                if ~l & 1:
                    A[l ^ 1] += x
                tmp = max(A[l], A[l ^ 1])
                A[l] -= tmp
                A[l ^ 1] -= tmp
                A[l >> 1] += tmp
                l >>= 1
        elif l == r:
            (A, N) = (self.A, self.N)
            l += N
            A[l] += x
            while l > 1:
                tmp = max(A[l], A[l ^ 1])
                A[l] -= tmp
                A[l ^ 1] -= tmp
                A[l >> 1] += tmp
                l >>= 1
        elif l < r:
            l += N - 1
            r += N + 1
            while l ^ r ^ 1:
                if ~l & 1:
                    A[l ^ 1] += x
                if r & 1:
                    A[r ^ 1] += x
                tmp = max(A[l], A[l ^ 1])
                A[l] -= tmp
                A[l ^ 1] -= tmp
                A[l >> 1] += tmp
                tmp = max(A[r], A[r ^ 1])
                A[r] -= tmp
                A[r ^ 1] -= tmp
                A[r >> 1] += tmp
                l >>= 1
                r >>= 1
            while l > 1:
                tmp = max(A[l], A[l ^ 1])
                A[l] -= tmp
                A[l ^ 1] -= tmp
                A[l >> 1] += tmp
                l >>= 1

    def query(self, l, r):
        (A, N) = (self.A, self.N)
        l += N
        r += N
        S = T = 0
        if l ^ r:
            while l ^ r ^ 1:
                S += A[l]
                T += A[r]
                if ~l & 1:
                    S = max(S, A[l ^ 1])
                if r & 1:
                    T = max(T, A[r ^ 1])
                l >>= 1
                r >>= 1
        S = max(A[l] + S, A[r] + T)
        while l > 1:
            l >>= 1
            S += A[l]
        return S

def solution():
    (n, k, A) = readis()
    t = SEGMENTTREE_ADD_MAX(k, n)
    E = [[] for _ in range(k + 1)]
    s = 0
    for _ in range(n):
        (a, b, c) = readis()
        E[k - b].append([a, c])
        s += c
    dp = 0
    for r in range(k + 1):
        for (l, c) in E[r]:
            t.update(0, l, c)
        dp = max(dp, t.A[1] - A * r)
        t.update(r, r, dp + r * A)
    print(s - dp)
for i in range(1 if 1 else readi()):
    solution()