結果

問題 No.2546 Many Arithmetic Sequences
ユーザー ShirotsumeShirotsume
提出日時 2023-07-26 15:26:20
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 3,611 bytes
コンパイル時間 501 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 171,936 KB
最終ジャッジ日時 2024-09-26 09:54:27
合計ジャッジ時間 25,148 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
69,632 KB
testcase_01 AC 70 ms
69,632 KB
testcase_02 AC 117 ms
80,128 KB
testcase_03 AC 669 ms
117,464 KB
testcase_04 AC 863 ms
144,040 KB
testcase_05 AC 796 ms
125,732 KB
testcase_06 AC 346 ms
101,244 KB
testcase_07 AC 490 ms
105,264 KB
testcase_08 AC 271 ms
95,056 KB
testcase_09 AC 351 ms
108,032 KB
testcase_10 AC 552 ms
142,080 KB
testcase_11 AC 597 ms
143,744 KB
testcase_12 AC 398 ms
113,296 KB
testcase_13 AC 691 ms
125,592 KB
testcase_14 AC 581 ms
134,144 KB
testcase_15 AC 303 ms
95,744 KB
testcase_16 AC 589 ms
132,656 KB
testcase_17 AC 905 ms
138,880 KB
testcase_18 AC 479 ms
116,348 KB
testcase_19 AC 570 ms
118,560 KB
testcase_20 AC 363 ms
104,976 KB
testcase_21 AC 536 ms
109,824 KB
testcase_22 AC 640 ms
125,280 KB
testcase_23 AC 1,128 ms
168,420 KB
testcase_24 AC 1,113 ms
166,268 KB
testcase_25 AC 1,078 ms
170,036 KB
testcase_26 AC 1,143 ms
167,992 KB
testcase_27 AC 1,170 ms
169,020 KB
testcase_28 AC 667 ms
169,172 KB
testcase_29 AC 639 ms
171,936 KB
testcase_30 AC 664 ms
171,628 KB
testcase_31 AC 673 ms
169,152 KB
testcase_32 AC 657 ms
171,752 KB
testcase_33 AC 80 ms
70,272 KB
testcase_34 AC 967 ms
166,456 KB
testcase_35 AC 83 ms
70,400 KB
testcase_36 AC 718 ms
170,900 KB
testcase_37 RE -
testcase_38 AC 88 ms
72,704 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))

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