結果

問題 No.1982 [Cherry 4th Tune B] 絶険
ユーザー lilictakalilictaka
提出日時 2022-06-30 19:06:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,510 ms / 3,000 ms
コード長 1,943 bytes
コンパイル時間 238 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 158,572 KB
最終ジャッジ日時 2024-05-03 15:43:54
合計ジャッジ時間 31,814 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
52,352 KB
testcase_01 AC 38 ms
52,224 KB
testcase_02 AC 50 ms
71,040 KB
testcase_03 AC 882 ms
114,132 KB
testcase_04 AC 966 ms
111,656 KB
testcase_05 AC 423 ms
101,188 KB
testcase_06 AC 816 ms
122,836 KB
testcase_07 AC 801 ms
123,284 KB
testcase_08 AC 919 ms
114,492 KB
testcase_09 AC 912 ms
126,048 KB
testcase_10 AC 738 ms
113,184 KB
testcase_11 AC 371 ms
96,256 KB
testcase_12 AC 972 ms
118,516 KB
testcase_13 AC 740 ms
101,596 KB
testcase_14 AC 426 ms
104,384 KB
testcase_15 AC 660 ms
99,168 KB
testcase_16 AC 511 ms
111,264 KB
testcase_17 AC 1,197 ms
140,472 KB
testcase_18 AC 1,051 ms
134,300 KB
testcase_19 AC 1,171 ms
139,508 KB
testcase_20 AC 395 ms
98,016 KB
testcase_21 AC 352 ms
104,008 KB
testcase_22 AC 786 ms
105,876 KB
testcase_23 AC 433 ms
98,284 KB
testcase_24 AC 446 ms
96,560 KB
testcase_25 AC 1,214 ms
129,344 KB
testcase_26 AC 1,214 ms
136,336 KB
testcase_27 AC 243 ms
86,400 KB
testcase_28 AC 851 ms
116,088 KB
testcase_29 AC 1,088 ms
135,988 KB
testcase_30 AC 397 ms
131,592 KB
testcase_31 AC 903 ms
117,740 KB
testcase_32 AC 1,510 ms
154,576 KB
testcase_33 AC 880 ms
157,908 KB
testcase_34 AC 910 ms
158,572 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