Submission #74603844

---

Source Code Expand

import bisect, heapq, sys, math, copy, itertools, decimal
from collections import defaultdict, deque
sys.setrecursionlimit(10**7)
def INT(): return int(input())
def MI(d=0): return map(lambda x:int(x)+d, input().split())
def MS(): return map(str, input().split())
def LI(d=0): return list(map(lambda x:int(x)+d, input().split()))
def LS(): return list(map(str, input().split()))
def pr_line(itr): print(*itr, sep='\n')
def pr_mtx(matrix): [print(*row) for row in matrix] 
dij = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dij2 = [[1, 0], [0, 1], [-1, 0], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]
INF = float('inf')

from atcoder.segtree import SegTree
INF = 1<<62

def op(x, y):
    return x + y

# opの単位元 op(data1, e) = data1
e = 0

#########################################


N, M, Q, K = MI()

shelf = defaultdict(list)
st = SegTree(op, e, [0]*N)

books = []
for _ in range(M):
    s, d = MI()
    s -= 1
    shelf[s].append(d)
    books.append((d, s))
    st.set(s, st.get(s) + 1)
books.sort()
books = deque(books)

query = []
for i in range(Q):
    l, r, t = MI()
    l -= 1
    r -= 1
    query.append((l, r, t, i))
query.sort(key=lambda x:x[2])


ans = [-1]*Q
for l, r, t, i in query:
    while books and books[0][0] < t:
        d, s = books.popleft()
        st.set(s, st.get(s) - 1)
    
    ans[i] = max(0, st.prod(l, r+1) - K)

pr_line(ans)

Submission Info

Judge Result