結果

問題 No.2546 Many Arithmetic Sequences
ユーザー ShirotsumeShirotsume
提出日時 2023-11-25 20:43:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,010 ms / 2,000 ms
コード長 3,650 bytes
コンパイル時間 740 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 171,680 KB
最終ジャッジ日時 2023-11-25 20:46:06
合計ジャッジ時間 22,343 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 66 ms
70,832 KB
testcase_01 AC 65 ms
70,832 KB
testcase_02 AC 119 ms
79,588 KB
testcase_03 AC 596 ms
117,488 KB
testcase_04 AC 768 ms
143,572 KB
testcase_05 AC 700 ms
125,668 KB
testcase_06 AC 321 ms
101,000 KB
testcase_07 AC 470 ms
104,860 KB
testcase_08 AC 249 ms
94,648 KB
testcase_09 AC 325 ms
107,336 KB
testcase_10 AC 507 ms
141,800 KB
testcase_11 AC 505 ms
143,548 KB
testcase_12 AC 342 ms
113,020 KB
testcase_13 AC 571 ms
125,328 KB
testcase_14 AC 481 ms
133,756 KB
testcase_15 AC 259 ms
95,384 KB
testcase_16 AC 490 ms
132,004 KB
testcase_17 AC 798 ms
138,124 KB
testcase_18 AC 457 ms
115,820 KB
testcase_19 AC 517 ms
118,436 KB
testcase_20 AC 333 ms
104,520 KB
testcase_21 AC 477 ms
109,212 KB
testcase_22 AC 601 ms
124,796 KB
testcase_23 AC 996 ms
168,000 KB
testcase_24 AC 996 ms
165,460 KB
testcase_25 AC 889 ms
169,356 KB
testcase_26 AC 982 ms
167,588 KB
testcase_27 AC 1,010 ms
167,852 KB
testcase_28 AC 594 ms
168,780 KB
testcase_29 AC 577 ms
171,268 KB
testcase_30 AC 585 ms
170,916 KB
testcase_31 AC 587 ms
169,256 KB
testcase_32 AC 612 ms
171,680 KB
testcase_33 AC 66 ms
70,832 KB
testcase_34 AC 872 ms
165,704 KB
testcase_35 AC 68 ms
70,832 KB
testcase_36 AC 625 ms
171,232 KB
testcase_37 AC 89 ms
78,172 KB
testcase_38 AC 73 ms
73,016 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