結果

問題 No.2404 Vertical Throw Up
ユーザー gr1msl3ygr1msl3y
提出日時 2023-08-15 13:28:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 593 ms / 2,000 ms
コード長 4,353 bytes
コンパイル時間 297 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 95,916 KB
最終ジャッジ日時 2024-05-03 01:00:05
合計ジャッジ時間 6,509 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
53,376 KB
testcase_01 AC 35 ms
52,992 KB
testcase_02 AC 38 ms
53,632 KB
testcase_03 AC 457 ms
90,924 KB
testcase_04 AC 396 ms
88,608 KB
testcase_05 AC 593 ms
95,916 KB
testcase_06 AC 48 ms
63,360 KB
testcase_07 AC 592 ms
95,340 KB
testcase_08 AC 465 ms
90,712 KB
testcase_09 AC 388 ms
87,724 KB
testcase_10 AC 198 ms
79,732 KB
testcase_11 AC 197 ms
80,496 KB
testcase_12 AC 178 ms
79,216 KB
testcase_13 AC 56 ms
69,760 KB
testcase_14 AC 77 ms
76,384 KB
testcase_15 AC 74 ms
76,416 KB
testcase_16 AC 60 ms
70,784 KB
testcase_17 AC 85 ms
76,808 KB
testcase_18 AC 83 ms
76,736 KB
testcase_19 AC 59 ms
69,760 KB
testcase_20 AC 59 ms
70,272 KB
testcase_21 AC 85 ms
76,528 KB
testcase_22 AC 60 ms
70,912 KB
testcase_23 AC 54 ms
67,456 KB
testcase_24 AC 75 ms
76,288 KB
testcase_25 AC 52 ms
66,304 KB
testcase_26 AC 74 ms
76,416 KB
testcase_27 AC 85 ms
76,672 KB
testcase_28 AC 62 ms
66,560 KB
testcase_29 AC 56 ms
63,744 KB
testcase_30 AC 51 ms
61,952 KB
testcase_31 AC 71 ms
69,888 KB
testcase_32 AC 48 ms
64,512 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, 0)
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