提出 #74602522

---

ソースコード 拡げる

import sys
input = sys.stdin.readline

N, M, Q, K = map(int, input().split())

books = []
for _ in range(M):
    s, d = map(int, input().split())
    books.append((d, s))  # sort by pages

queries = []
for i in range(Q):
    l, r, t = map(int, input().split())
    queries.append((t, l, r, i))

# sort descending
books.sort(reverse=True)
queries.sort(reverse=True)

# Fenwick Tree
BIT = [0] * (N + 1)

def update(i):
    while i <= N:
        BIT[i] += 1
        i += i & -i

def query(i):
    s = 0
    while i > 0:
        s += BIT[i]
        i -= i & -i
    return s

ans = [0] * Q

i = 0
for t, l, r, idx in queries:
    while i < M and books[i][0] >= t:
        _, shelf = books[i]
        update(shelf)
        i += 1
    
    count = query(r) - query(l - 1)
    ans[idx] = max(count - K, 0)

print("\n".join(map(str, ans)))

提出情報

ジャッジ結果