結果

問題 No.2546 Many Arithmetic Sequences
ユーザー ShirotsumeShirotsume
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 63 ms
69,632 KB
testcase_01 AC 62 ms
69,888 KB
testcase_02 AC 110 ms
80,088 KB
testcase_03 AC 529 ms
117,600 KB
testcase_04 AC 724 ms
143,704 KB
testcase_05 AC 657 ms
125,180 KB
testcase_06 AC 291 ms
101,632 KB
testcase_07 AC 416 ms
105,008 KB
testcase_08 AC 225 ms
94,912 KB
testcase_09 AC 288 ms
107,812 KB
testcase_10 AC 446 ms
142,592 KB
testcase_11 AC 434 ms
143,992 KB
testcase_12 AC 318 ms
113,308 KB
testcase_13 AC 526 ms
125,464 KB
testcase_14 AC 452 ms
134,016 KB
testcase_15 AC 236 ms
95,592 KB
testcase_16 AC 464 ms
132,736 KB
testcase_17 AC 772 ms
138,944 KB
testcase_18 AC 404 ms
116,480 KB
testcase_19 AC 492 ms
118,700 KB
testcase_20 AC 299 ms
105,184 KB
testcase_21 AC 444 ms
109,536 KB
testcase_22 AC 540 ms
125,468 KB
testcase_23 AC 908 ms
168,284 KB
testcase_24 AC 896 ms
165,996 KB
testcase_25 AC 852 ms
170,200 KB
testcase_26 AC 931 ms
167,864 KB
testcase_27 AC 905 ms
168,128 KB
testcase_28 AC 520 ms
169,192 KB
testcase_29 AC 515 ms
171,684 KB
testcase_30 AC 512 ms
171,072 KB
testcase_31 AC 533 ms
170,040 KB
testcase_32 AC 527 ms
172,272 KB
testcase_33 AC 62 ms
69,888 KB
testcase_34 AC 801 ms
165,940 KB
testcase_35 AC 65 ms
70,528 KB
testcase_36 AC 574 ms
171,028 KB
testcase_37 AC 81 ms
78,720 KB
testcase_38 AC 69 ms
72,960 KB
権限があれば一括ダウンロードができます

ソースコード

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