結果

問題 No.1982 [Cherry 4th Tune B] 絶険
ユーザー lilictakalilictaka
提出日時 2022-06-30 19:06:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,471 ms / 3,000 ms
コード長 1,943 bytes
コンパイル時間 480 ms
コンパイル使用メモリ 87,208 KB
実行使用メモリ 161,592 KB
最終ジャッジ日時 2023-08-16 06:38:08
合計ジャッジ時間 36,511 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 71 ms
71,376 KB
testcase_01 AC 70 ms
71,524 KB
testcase_02 AC 81 ms
79,148 KB
testcase_03 AC 887 ms
115,028 KB
testcase_04 AC 936 ms
113,672 KB
testcase_05 AC 441 ms
103,168 KB
testcase_06 AC 822 ms
123,744 KB
testcase_07 AC 834 ms
124,292 KB
testcase_08 AC 910 ms
117,000 KB
testcase_09 AC 901 ms
127,464 KB
testcase_10 AC 757 ms
113,804 KB
testcase_11 AC 400 ms
98,736 KB
testcase_12 AC 994 ms
119,872 KB
testcase_13 AC 756 ms
103,208 KB
testcase_14 AC 442 ms
105,376 KB
testcase_15 AC 653 ms
100,572 KB
testcase_16 AC 557 ms
112,816 KB
testcase_17 AC 1,184 ms
142,208 KB
testcase_18 AC 1,116 ms
135,888 KB
testcase_19 AC 1,154 ms
140,400 KB
testcase_20 AC 418 ms
99,564 KB
testcase_21 AC 380 ms
105,620 KB
testcase_22 AC 798 ms
106,888 KB
testcase_23 AC 449 ms
99,444 KB
testcase_24 AC 428 ms
97,056 KB
testcase_25 AC 1,155 ms
130,900 KB
testcase_26 AC 1,175 ms
136,908 KB
testcase_27 AC 257 ms
87,756 KB
testcase_28 AC 842 ms
118,524 KB
testcase_29 AC 1,077 ms
137,668 KB
testcase_30 AC 455 ms
133,524 KB
testcase_31 AC 881 ms
118,336 KB
testcase_32 AC 1,471 ms
155,672 KB
testcase_33 AC 871 ms
159,920 KB
testcase_34 AC 960 ms
161,592 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.n0 = 2**(n-1).bit_length()
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def init(self, A):
        self.data[1:] = A
        for i in range(1, self.n):
            if i + (i & -i) <= self.n:
                self.data[i + (i & -i)] += self.data[i]
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):#1-index
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
    def lower_bound(self, x):
        w = i = 0
        k = self.n0
        while k:
            if i+k <= self.n and w + self.data[i+k] <= x:
                w += self.data[i+k]
                i += k
            k >>= 1
        # assert self.get(0, i) <= x < self.get(0, i+1)
        return i+1
from sys import stdin
input = stdin.readline
II = lambda :int(input())
MI = lambda :map(int,input().split())
LI = lambda :list(map(int,input().split()))
ANS = []
#文字列出力はListでつくってから''.join(ANS),文字列結合は遅い
N,K,Q = MI()
memo = []
board = [[] for _ in range(N)]
query = [[] for _ in range(N)]
bt = BIT(K)
for i in range(K):
    l,r,c,h = map(int,input().split())
    l-=1
    memo.append(c)
    board[l].append((h,i+1))
    if r < N:
        board[r].append((-h,i+1))
for q in range(Q):
    l,x = map(int,input().split())
    l-=1
    query[l].append((q,x))
for l in range(N):
    for h,ind in board[l]:
        bt.add(ind,h)
    for q,x in query[l]:
        index = bt.lower_bound(x-1)
        ANS.append((q,index))
ANS.sort()
for _,index in ANS:
    if index == K + 1:
        print(-1)
    else:
        print(memo[index-1])
0