結果

問題 No.2404 Vertical Throw Up
ユーザー gr1msl3ygr1msl3y
提出日時 2023-08-15 13:27:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 585 ms / 2,000 ms
コード長 4,353 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 94,080 KB
最終ジャッジ日時 2024-05-03 00:59:57
合計ジャッジ時間 6,905 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,248 KB
testcase_01 AC 39 ms
53,504 KB
testcase_02 AC 40 ms
53,120 KB
testcase_03 AC 480 ms
90,144 KB
testcase_04 AC 424 ms
87,692 KB
testcase_05 AC 585 ms
94,080 KB
testcase_06 AC 53 ms
62,464 KB
testcase_07 AC 580 ms
93,944 KB
testcase_08 AC 485 ms
90,764 KB
testcase_09 AC 422 ms
87,284 KB
testcase_10 AC 216 ms
79,976 KB
testcase_11 AC 211 ms
79,780 KB
testcase_12 AC 195 ms
79,460 KB
testcase_13 AC 62 ms
66,432 KB
testcase_14 AC 79 ms
74,212 KB
testcase_15 AC 73 ms
70,784 KB
testcase_16 AC 65 ms
67,328 KB
testcase_17 AC 87 ms
75,008 KB
testcase_18 AC 87 ms
76,416 KB
testcase_19 AC 62 ms
66,176 KB
testcase_20 AC 65 ms
67,584 KB
testcase_21 AC 84 ms
75,972 KB
testcase_22 AC 63 ms
67,456 KB
testcase_23 AC 60 ms
65,024 KB
testcase_24 AC 76 ms
73,160 KB
testcase_25 AC 56 ms
63,232 KB
testcase_26 AC 72 ms
71,552 KB
testcase_27 AC 77 ms
73,088 KB
testcase_28 AC 58 ms
64,384 KB
testcase_29 AC 51 ms
62,080 KB
testcase_30 AC 49 ms
61,568 KB
testcase_31 AC 62 ms
65,920 KB
testcase_32 AC 51 ms
62,848 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect_left


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def sumrange(self, i, j):
        si = self.sum(i - 1)
        sj = self.sum(j)
        return sj - si

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def lower_bound(self, w):
        if w <= 0:
            return 0
        x = 0
        r = 1 << (self.size).bit_length()
        while r > 0:
            if x+r < self.size and self.tree[x+r] < w:
                w -= self.tree[x+r]
                x += r
            r = r >> 1
        return x


class ConvexHullTrick_General():

    def isneed(self, ismax, f1, f2, f3):
        va = (f3[1]-f2[1])*(f2[0]-f1[0])
        vb = (f2[1]-f1[1])*(f3[0]-f2[0])
        if ismax:
            return va < vb
        else:
            return va > vb

    def calc_value(self, x, line):
        a, b = line
        return a*x+b

    def __init__(self, lines_list, INF, ismax, isMonoq_get):
        self.ISMAX = ismax
        self.lines = [INF]+lines_list
        self.lines.sort(reverse=not self.ISMAX)
        self.state = Bit(len(self.lines)+2)
        self.state.add(0, 1)
        self.ct_all = 1
        self.ISMONOQ = isMonoq_get

    def add_line(self, line):
        ind = bisect_left(self.lines, line)
        ct = self.state.sum(ind-1)
        if 0 < ct < self.ct_all:
            indl = self.state.lower_bound(ct)
            indr = self.state.lower_bound(ct+1)
            if not self.isneed(1, self.lines[indl], self.lines[ind], self.lines[indr]):
                return
        self.state.add(ind, 1)
        self.ct_all += 1
        ct += 1
        if ct < self.ct_all:
            indr0 = self.state.lower_bound(ct+1)
        while ct+1 < self.ct_all:
            indr1 = self.state.lower_bound(ct+2)
            if self.isneed(self.ISMAX, line, self.lines[indr0], self.lines[indr1]):
                break
            else:
                self.state.add(indr0, -1)
                self.ct_all -= 1
                indr0 = indr1
        if ct > 1:
            indl1 = self.state.lower_bound(ct-1)
        while ct > 2:
            indl0 = self.state.lower_bound(ct-2)
            if self.isneed(self.ISMAX, self.lines[indl0], self.lines[indl1], line):
                break
            else:
                self.state.add(indl1, -1)
                ct -= 1
                self.ct_all -= 1
                indl1 = indl0

    def get_monoq(self, x):
        ind0 = self.state.lower_bound(1)
        res0 = self.calc_value(x, self.lines[ind0])
        while self.ct_all > 1:
            ind1 = self.state.lower_bound(2)
            res1 = self.calc_value(x, self.lines[ind1])
            if res0 < res1:
                self.state.add(ind0, -1)
                ind0 = ind1
                res0 = res1
                self.ct_all -= 1
            else:
                break
        return res0

    def get_general(self, x):
        l = 1
        r = self.ct_all
        while r-l > 2:
            c = (r-l)//3
            m0 = l+c
            m1 = r-c
            ind0 = self.state.lower_bound(m0)
            ind1 = self.state.lower_bound(m1)
            if (self.calc_value(x, self.lines[ind0]) < self.calc_value(x, self.lines[ind1])) ^ self.ISMAX:
                r = m1
            else:
                l = m0
        task = [self.calc_value(x, self.lines[self.state.lower_bound(i)])
                for i in range(l, r+1)]
        if self.ISMAX:
            return max(task)
        else:
            return min(task)

    def get(self, x):
        if self.ISMONOQ:
            return self.get_monoq(x)
        else:
            return self.get_general(x)


Ga = int(input())
Q = int(input())
query = [list(map(int, input().split())) for _ in range(Q)]
lines = []
for q in query:
    if len(q) == 3:
        s, t = q[1:]
        lines.append([s+t, -s*t])


ans = []
cht = ConvexHullTrick_General(lines, [-1, -10**10], 1, 1)
for q in query:
    if q[0] == 1:
        s, t = q[1:]
        cht.add_line([s+t, -s*t])
    else:
        t = q[1]
        res = cht.get(t)
        ans.append(max(0, (-t**2+res)*Ga))

print(*ans, sep='\n')
0