結果

問題 No.2546 Many Arithmetic Sequences
コンテスト
ユーザー Shirotsume
提出日時 2023-11-25 20:43:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 931 ms / 2,000 ms
コード長 3,650 bytes
コンパイル時間 403 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 172,272 KB
最終ジャッジ日時 2024-09-26 11:19:53
合計ジャッジ時間 20,008 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

from typing import List, Tuple
from bisect import bisect_left
import sys, time, random, heapq
from collections import deque, Counter, defaultdict
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
inf = 2 ** 63 - 1
mod = 998244353
class LiChaoTree:
    def __init__(self, variables: List[int]) -> None:
        if any(not a < b for a, b in zip(variables, variables[1:])):
            raise ValueError('variables must be sorted')
        self.inf = (1 << 63) - 1
        self.n = len(variables)
        self.size = 1 << (self.n - 1).bit_length()
        self.variables = variables + [self.inf] * (self.size - self.n)
        self.a = [0] * (2 * self.size)
        self.b = [self.inf] * (2 * self.size)

    def __findpos(self, x: int) -> Tuple[int, bool]:
        p = bisect_left(self.variables, x)
        if p >= self.n or self.variables[p] != x: return p, False
        return p, True

    def __add(self, a: int, b: int, idx: int, lpos: int, rpos: int) -> None:
        while True:
            mpos = (lpos + rpos) >> 1
            lx = self.variables[lpos]
            mx = self.variables[mpos]
            rx = self.variables[rpos - 1]
            ai, bi = self.a[idx], self.b[idx]
            lu = a * lx + b < ai * lx + bi
            mu = a * mx + b < ai * mx + bi
            ru = a * rx + b < ai * rx + bi
            if lu and ru:
                self.a[idx], self.b[idx] = a, b
                return
            if not lu and not ru:
                return
            if mu:
                self.a[idx], self.b[idx], a, b = a, b, self.a[idx], self.b[idx]
            if lu != mu:
                rpos = mpos
                idx = 2 * idx
            else:
                lpos = mpos
                idx = 2 * idx + 1

    def add_line(self, a: int, b: int) -> None:
        self.__add(a, b, 1, 0, self.size)

    def add_segment(self, a: int, b: int, l: int, r: int) -> None:
        lpos, _ = self.__findpos(l)
        rpos, _ = self.__findpos(r)
        lidx = lpos + self.size
        ridx = rpos + self.size
        sz = 1
        while lidx < ridx:
            if lidx & 1:
                self.__add(a, b, lidx, lpos, lpos + sz)
                lidx += 1
                lpos += sz
            if ridx & 1:
                ridx -= 1
                self.__add(a, b, ridx, rpos - sz, rpos)
                rpos -= sz
            lidx >>= 1
            ridx >>= 1
            sz <<= 1

    def get_min(self, x: int) -> int:
        p, f = self.__findpos(x)
        if not f: raise ValueError('x is not in variables')
        idx = p + self.size
        res = self.a[idx] * x + self.b[idx]
        while idx > 1:
            idx >>= 1
            res = min(res, self.a[idx] * x + self.b[idx])
        return res
n, m = mi()
AD = [li() for _ in range(n)]
plus = []
minus = []

for a, d in AD:
    if d > 0:
        plus.append((a, d))
    else:
        minus.append((a, d))

p = [-inf] * (m + 1)
p[0] = 0
plus.sort(key = lambda x: x[1], reverse=True)
L = LiChaoTree(list(range(0, m + 1)))
for a, d in plus:
    L.add_line(-d, -2 * a + d)
if plus:
    for i in range(1, m + 1):
        p[i] = -L.get_min(i) * i // 2


q = [-inf] * (m + 1)
q[0] = 0
H = []

for a, d in minus:
    heapq.heappush(H, (-a, d))

heapq.heappush(H, (10 ** 8, -10 ** 8))
for i in range(1, m + 1):
    a, d = heapq.heappop(H)
    a = -a
    q[i] = q[i - 1] + a
    heapq.heappush(H, (-(a + d), d))
ans = -inf
maxi = -1
for i in range(0, m + 1):
    if ans <= p[i] + q[m - i]:
        ans = max(ans, p[i] + q[m - i])
        maxi = i

print(ans)
print(m, maxi, file=sys.stderr)
0