結果

問題 No.1982 [Cherry 4th Tune B] 絶険
コンテスト
ユーザー lilictaka
提出日時 2022-06-30 19:06:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,353 ms / 3,000 ms
コード長 1,943 bytes
コンパイル時間 210 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 159,072 KB
最終ジャッジ日時 2024-11-24 17:46:58
合計ジャッジ時間 29,765 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

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