提出 #74602827

---

ソースコード 拡げる

import sys

def solve():
    # Read all tokens from standard input efficiently
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    Q = int(input_data[2])
    K = int(input_data[3])
    
    events = []
    idx = 4
    
    # Read all books and register them as events of Type 2
    for _ in range(M):
        S = int(input_data[idx])
        D = int(input_data[idx+1])
        # Format: (Value/Time, Type, Shelf)
        events.append((D, 2, S))
        idx += 2
        
    # Read all queries and register them as events of Type 1
    for j in range(Q):
        L = int(input_data[idx])
        R = int(input_data[idx+1])
        T = int(input_data[idx+2])
        # Format: (Value/Time, Type, Left, Right, Original Query Index)
        events.append((T, 1, L, R, j))
        idx += 3
        
    # Sort events descendingly by value (page counts). 
    # Because 2 > 1, if values are equal, Type 2 (Add Book) events come before Type 1 (Queries).
    events.sort(reverse=True)
    
    # Binary Indexed Tree (Fenwick Tree) Initialization
    tree = [0] * (N + 1)
    
    def add(i, delta):
        while i <= N:
            tree[i] += delta
            i += i & (-i)
            
    def query(i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & (-i)
        return s
        
    ans = [0] * Q
    
    # Process events
    for ev in events:
        if ev[1] == 2:   # Add Book Event
            S = ev[2]
            add(S, 1)
        else:            # Search Query Event
            L = ev[2]
            R = ev[3]
            qid = ev[4]
            # Calculate the current range sum of matching books
            count = query(R) - query(L - 1)
            # Subtract K and apply lower bound 0
            ans[qid] = count - K if count > K else 0
            
    # Efficiently write output
    sys.stdout.write('\n'.join(map(str, ans)) + '\n')

if __name__ == '__main__':
    solve()

提出情報

ジャッジ結果