結果

問題 No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに
ユーザー 👑 KazunKazun
提出日時 2022-08-29 00:56:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,156 ms / 6,000 ms
コード長 4,646 bytes
コンパイル時間 654 ms
コンパイル使用メモリ 86,360 KB
実行使用メモリ 175,252 KB
最終ジャッジ日時 2023-09-08 20:03:16
合計ジャッジ時間 65,685 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 82 ms
71,284 KB
testcase_01 AC 81 ms
71,068 KB
testcase_02 AC 82 ms
71,168 KB
testcase_03 AC 1,184 ms
124,556 KB
testcase_04 AC 1,545 ms
134,632 KB
testcase_05 AC 1,052 ms
120,548 KB
testcase_06 AC 1,306 ms
132,780 KB
testcase_07 AC 1,546 ms
143,104 KB
testcase_08 AC 1,287 ms
131,648 KB
testcase_09 AC 961 ms
114,808 KB
testcase_10 AC 868 ms
112,688 KB
testcase_11 AC 1,120 ms
121,184 KB
testcase_12 AC 1,140 ms
121,276 KB
testcase_13 AC 836 ms
110,132 KB
testcase_14 AC 651 ms
97,484 KB
testcase_15 AC 1,627 ms
146,000 KB
testcase_16 AC 1,495 ms
142,308 KB
testcase_17 AC 582 ms
95,180 KB
testcase_18 AC 1,852 ms
155,664 KB
testcase_19 AC 1,996 ms
175,252 KB
testcase_20 AC 1,946 ms
159,200 KB
testcase_21 AC 1,906 ms
156,216 KB
testcase_22 AC 1,969 ms
173,428 KB
testcase_23 AC 1,982 ms
174,056 KB
testcase_24 AC 1,895 ms
171,488 KB
testcase_25 AC 1,946 ms
157,892 KB
testcase_26 AC 1,930 ms
155,804 KB
testcase_27 AC 1,963 ms
173,912 KB
testcase_28 AC 1,915 ms
156,808 KB
testcase_29 AC 2,007 ms
160,036 KB
testcase_30 AC 1,963 ms
172,900 KB
testcase_31 AC 2,156 ms
155,516 KB
testcase_32 AC 1,937 ms
171,148 KB
testcase_33 AC 1,773 ms
157,576 KB
testcase_34 AC 1,774 ms
155,652 KB
testcase_35 AC 1,808 ms
157,608 KB
testcase_36 AC 1,738 ms
156,764 KB
testcase_37 AC 1,696 ms
157,180 KB
testcase_38 AC 217 ms
95,652 KB
testcase_39 AC 640 ms
96,556 KB
testcase_40 AC 939 ms
129,980 KB
testcase_41 AC 79 ms
71,172 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Binary_Indexed_Tree():
    def __init__(self, L, calc, unit, inv, index=1):
        """ calc を演算とする N 項の Binary Indexed Tree を作成
        calc: 演算 (2変数関数, 可換群)
        unit: 群 calc の単位元 (x+e=e+x=xを満たすe)
        inv : 群 calc の逆元 (1変数関数, x+inv(x)=inv(x)+x=e をみたす inv(x))
        """
        self.calc=calc
        self.unit=unit
        self.inv=inv
        self.index=index

        N=len(L)
        d=max(1,(N-1).bit_length())
        k=2**d

        X=[None]+[unit]*k

        self.num=k
        self.depth=d

        if L:
            for i in range(len(L)):
                p=i+1
                while p<=k:
                    X[p]=self.calc(X[p],L[i])
                    p+=p&(-p)
        self.data=X

    def index_number(self, k, index=1):
        """ 第 k 要素の値を出力する.
        k    : 数列の要素
        index: 先頭の要素の番号
        """
        return self.sum(k,k,index)

    def add(self, k, x, index=1):
        """ 第 k 要素に x を加え, 更新を行う.
        k    : 数列の要素
        x    : 加える値
        index: 先頭の要素の番号
        """
        data=self.data; calc=self.calc
        p=k+(1-index)
        while p<=self.num:
            data[p]=calc(self.data[p],x)
            p+=p&(-p)

    def update(self, k, x, index=1):
        """ 第 k 要素を x に変え, 更新を行う.
        k: 数列の要素
        x: 更新後の値
        """

        a=self.index_number(k,index)
        y=self.calc(self.inv(a),x)

        self.add(k,y,index)

    def sum(self, From, To, index=1):
        """ 第 From 要素から第 To 要素までの総和を求める.
        ※From!=1を使うならば, 群でなくてはならない.
        From : 始まり
        To   : 終わり
        index: 先頭の要素の番号
        """
        alpha=max(1,From+(1-index))
        beta=min(self.num,To+(1-index))

        if alpha>beta:
            return self.unit
        elif alpha==1:
            return self.__section(beta)
        else:
            return self.calc(self.inv(self.__section(alpha-1)),self.__section(beta))

    def __section(self,x):
        """ B[1]+...+B[x] を求める. """
        data=self.data; calc=self.calc
        S=self.unit
        while x>0:
            S=calc(data[x],S)
            x-=x&(-x)
        return S

    def all_sum(self):
        return self.data[-1]

    def binary_search(self, cond, index=1):
        """ cond(B[1]+...+B[k]) を満たす最小の k を返す.

        cond: 単調増加

        ※ cond(unit)=True の場合の返り値は index-1
        ※ cond(B[1]+...+B[k]) なる k が存在しない場合の返り値は self.num+index
        """

        if cond(self.unit):
            return index-1

        j=0
        r=self.num
        t=r
        data=self.data; calc=self.calc
        alpha=self.unit

        for _ in range(self.depth+1):
            if j+t<=self.num:
                beta=calc(alpha,data[j+t])
                if not cond(beta):
                    alpha=beta
                    j+=t
            t>>=1

        return j+index

    def __getitem__(self,index):
        if isinstance(index,int):
            return self.index_number(index,self.index)
        else:
            return [self.index_number(t,self.index) for t in index]

    def __setitem__(self,index,val):
        self.update(index,val,self.index)
#==================================================
from heapq import heapify,heappush,heappop
from operator import add,neg
import sys

input=sys.stdin.readline
write=sys.stdout.write

#==================================================
#入力
N=int(input())

A=[0]*N; T=[0]*N
for i in range(N):
    A[i],T[i]=map(int,input().split())

Q=int(input())
D=[0]*Q; L=[0]*Q; R=[0]*Q
for q in range(Q):
    D[q],L[q],R[q]=map(int,input().split())
    L[q]-=1; R[q]-=1

#==================================================
# 準備
Query=sorted(range(Q), key=lambda j:D[j])

E=[(T[i],i) for i in range(N)]
heapify(E)

#==================================================
# 本計算

def add(f,g):
    return (f[0]+g[0], f[1]+g[1])

def neg(f):
    return (-f[0], -f[1])

B=Binary_Indexed_Tree([(a,0) for a in A], add, (0,0), neg, 0)

Ans=[0]*Q
Mode=[0]*N

for q in Query:
    while bool(E) and E[0][0]<=D[q]:
        a,i=heappop(E)
        if Mode[i]==0:
            B.update(i, (A[i]+T[i]-1,-1),0)
            heappush(E,(A[i]+T[i],i))
        else:
            B.update(i, (0,0),0)

        Mode[i]+=1
    a,b=B.sum(L[q],R[q],0)
    Ans[q]=a+b*D[q]

write("\n".join(map(str,Ans)))
0