結果

問題 No.2546 Many Arithmetic Sequences
ユーザー ShirotsumeShirotsume
提出日時 2023-07-26 15:26:20
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 3,611 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 171,680 KB
最終ジャッジ日時 2023-11-25 01:26:42
合計ジャッジ時間 19,200 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 60 ms
70,704 KB
testcase_01 AC 66 ms
70,704 KB
testcase_02 AC 102 ms
79,460 KB
testcase_03 AC 516 ms
117,428 KB
testcase_04 AC 701 ms
143,576 KB
testcase_05 AC 635 ms
125,008 KB
testcase_06 AC 293 ms
101,000 KB
testcase_07 AC 412 ms
104,856 KB
testcase_08 AC 226 ms
94,648 KB
testcase_09 AC 288 ms
107,336 KB
testcase_10 AC 446 ms
141,800 KB
testcase_11 AC 447 ms
143,548 KB
testcase_12 AC 334 ms
113,016 KB
testcase_13 AC 529 ms
125,320 KB
testcase_14 AC 457 ms
133,756 KB
testcase_15 AC 230 ms
94,872 KB
testcase_16 AC 448 ms
132,004 KB
testcase_17 AC 712 ms
138,128 KB
testcase_18 AC 385 ms
115,824 KB
testcase_19 AC 459 ms
118,440 KB
testcase_20 AC 299 ms
104,636 KB
testcase_21 AC 447 ms
109,196 KB
testcase_22 AC 524 ms
124,796 KB
testcase_23 AC 868 ms
168,004 KB
testcase_24 AC 903 ms
165,488 KB
testcase_25 AC 803 ms
169,312 KB
testcase_26 AC 885 ms
167,588 KB
testcase_27 AC 906 ms
168,364 KB
testcase_28 AC 496 ms
169,272 KB
testcase_29 AC 492 ms
171,268 KB
testcase_30 AC 478 ms
170,908 KB
testcase_31 AC 510 ms
169,256 KB
testcase_32 AC 497 ms
171,680 KB
testcase_33 AC 61 ms
70,704 KB
testcase_34 AC 756 ms
165,624 KB
testcase_35 AC 60 ms
70,704 KB
testcase_36 AC 557 ms
171,104 KB
testcase_37 RE -
権限があれば一括ダウンロードができます

ソースコード

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))

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