Vasya and Maximum Profit (Codeforces 1107G)
Tags: DP, dsu

Vasya got really tired of these credits (from problem F) and now wants to earn the money himself! He decided to make a contest to gain a profit.Vasya has $$$n$$$ problems to choose from. They are numbered from $$$1$$$ to $$$n$$$. The difficulty of the $$$i$$$-th problem is $$$d_i$$$. Moreover, the problems are given in the increasing order by their difficulties. The difficulties of all tasks are pairwise distinct. In order to add the $$$i$$$-th problem to the contest you need to pay $$$c_i$$$ burles to its author. For each problem in the contest Vasya gets $$$a$$$ burles.In order to create a contest he needs to choose a consecutive subsegment of tasks.So the total earnings for the contest are calculated as follows:   if Vasya takes problem $$$i$$$ to the contest, he needs to pay $$$c_i$$$ to its author;  for each problem in the contest Vasya gets $$$a$$$ burles;  let $$$gap(l, r) = \max\limits_{l \le i < r} (d_{i + 1} - d_i)^2$$$. If Vasya takes all the tasks with indices from $$$l$$$ to $$$r$$$ to the contest, he also needs to pay $$$gap(l, r)$$$. If $$$l = r$$$ then $$$gap(l, r) = 0$$$. Calculate the maximum profit that Vasya can earn by taking a consecutive segment of tasks.

Input: The first line contains two integers $$$n$$$ and $$$a$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$1 \le a \le 10^9$$$) — the number of proposed tasks and the profit for a single problem, respectively.Each of the next $$$n$$$ lines contains two integers $$$d_i$$$ and $$$c_i$$$ ($$$1 \le d_i, c_i \le 10^9, d_i < d_{i+1}$$$).

Output: Print one integer — maximum amount of burles Vasya can earn.


Sample Inputs:
5 10
1 15
5 3
6 11
7 2
11 22

3 5
1 8
2 19
3 11

Sample Outputs:
13

0

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

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
    else:
        root[rs] = rt
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False
(n, a) = map(int, input().split())
(d, c) = ([], [0])
for _ in range(n):
    (d0, c0) = map(int, input().split())
    d.append(d0)
    c.append(a - c0)
ans = max(c)
for i in range(1, n + 1):
    c[i] += c[i - 1]
x = defaultdict(lambda : [])
for i in range(n - 1):
    x[d[i + 1] - d[i]].append(i)
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
mi = c[:n]
ma = c[1:]
for i in sorted(x.keys()):
    g = i * i
    for j in x[i]:
        k = j + 1
        (rj, rk) = (get_root(j), get_root(k))
        ans = max(ans, ma[rk] - mi[rj] - g)
        unite(j, k)
        r0 = get_root(j)
        (mi[r0], ma[r0]) = (min(mi[rj], mi[rk]), max(ma[rj], ma[rk]))
print(ans)

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

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
    else:
        root[rs] = rt
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False
(n, a) = map(int, input().split())
(d, c) = ([], [0])
for _ in range(n):
    (d0, c0) = map(int, input().split())
    d.append(d0)
    c.append(a - c0)
ans = max(c)
for i in range(1, n + 1):
    c[i] += c[i - 1]
x = [(d[i + 1] - d[i]) * n + i for i in range(n - 1)]
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
mi = c[:n]
ma = c[1:]
for i in sorted(x):
    g = i // n * (i // n)
    j = i % n
    k = j + 1
    (rj, rk) = (get_root(j), get_root(k))
    ans = max(ans, ma[rk] - mi[rj] - g)
    unite(j, k)
    r0 = get_root(j)
    (mi[r0], ma[r0]) = (min(mi[rj], mi[rk]), max(ma[rj], ma[rk]))
print(ans)

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

def sparse_table(a):
    (table1, table2) = ([], [])
    (s0, t0, l) = (list(a), list(a), 1)
    table1.append(s0)
    table2.append(t0)
    while 2 * l <= len(a):
        s = [min(s0[i], s0[i + l]) for i in range(len(s0) - l)]
        t = [max(t0[i], t0[i + l]) for i in range(len(t0) - l)]
        table1.append(list(s))
        table2.append(list(t))
        s0 = s
        t0 = t
        l *= 2
    return (table1, table2)

def get_min(l, r):
    d = len(bin(r - l + 1)) - 3
    ans = min(table1[d][l], table1[d][r - pow2[d] + 1])
    return ans

def get_max(l, r):
    d = len(bin(r - l + 1)) - 3
    ans = max(table2[d][l], table2[d][r - pow2[d] + 1])
    return ans

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
        size[rs] += size[rt]
    else:
        root[rs] = rt
        size[rt] += size[rs]
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False
(n, a) = map(int, input().split())
(d, c) = ([], [0])
for _ in range(n):
    (d0, c0) = map(int, input().split())
    d.append(d0)
    c.append(a - c0)
ans = max(c)
for i in range(1, n + 1):
    c[i] += c[i - 1]
(table1, table2) = sparse_table(c)
pow2 = [1]
for _ in range(20):
    pow2.append(2 * pow2[-1])
x = defaultdict(lambda : [])
for i in range(n - 1):
    x[d[i + 1] - d[i]].append(i)
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
size = [1 for _ in range(n)]
mi = [i for i in range(n)]
ma = [i for i in range(n)]
for i in sorted(x.keys()):
    g = i * i
    for j in x[i]:
        k = j + 1
        (rj, rk) = (get_root(j), get_root(k))
        (l, r) = (mi[rj], ma[rk])
        unite(j, k)
        r0 = get_root(j)
        (mi[r0], ma[r0]) = (l, r)
        ans = max(ans, get_max(k + 1, r + 1) - get_min(l, j) - g)
print(ans)