結果

問題 No.2404 Vertical Throw Up
ユーザー gr1msl3ygr1msl3y
提出日時 2023-08-15 13:21:49
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,345 bytes
コンパイル時間 130 ms
コンパイル使用メモリ 82,444 KB
実行使用メモリ 90,792 KB
最終ジャッジ日時 2024-05-03 00:53:43
合計ジャッジ時間 4,022 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,248 KB
testcase_01 AC 38 ms
53,120 KB
testcase_02 AC 37 ms
52,864 KB
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
権限があれば一括ダウンロードができます

ソースコード

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