結果

問題 No.2404 Vertical Throw Up
ユーザー gr1msl3y
提出日時 2023-08-15 13:27:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 494 ms / 2,000 ms
コード長 4,353 bytes
コンパイル時間 263 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 94,592 KB
最終ジャッジ日時 2024-11-23 20:52:24
合計ジャッジ時間 6,203 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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')
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0