提出 #74619833

---

ソースコード 拡げる

import sys

def solve():
    input = sys.stdin.read().split()
    if not input: return
    N = int(input[0])
    Q = int(input[1])
    
    employees = []
    idx = 2
    for i in range(N):
        employees.append((int(input[idx]), int(input[idx+1])))
        idx += 2
    
    # Sort employees by coordinate
    employees.sort()
    
    # Coordinate compress scores
    all_scores = sorted(list(set(e[1] for e in employees)))
    score_map = {val: i for i, val in enumerate(all_scores)}
    scores = [score_map[e[1]] for e in employees]
    coords = [e[0] for e in employees]

    queries = []
    for i in range(Q):
        l_coord = int(input[idx])
        r_coord = int(input[idx+1])
        idx += 2
        
        # Binary search to find indices in our sorted employee list
        import bisect
        L = bisect.bisect_left(coords, l_coord)
        R = bisect.bisect_right(coords, r_coord) - 1
        if L <= R:
            queries.append((L, R, i))
        else:
            queries.append((-1, -1, i))

    # Mo's Algorithm
    block_size = int(N**0.5) + 1
    queries.sort(key=lambda x: (x[0] // block_size, x[1] if (x[0] // block_size) % 2 == 0 else -x[1]))

    ans = [0] * Q
    cnt = [0] * len(all_scores)
    curr_L, curr_R = 0, -1
    dups_pair_sum = 0
    K = 0

    def add(idx):
        nonlocal dups_pair_sum, K
        v = scores[idx]
        dups_pair_sum -= cnt[v] * (cnt[v] - 1) // 2
        cnt[v] += 1
        dups_pair_sum += cnt[v] * (cnt[v] - 1) // 2
        K += 1

    def remove(idx):
        nonlocal dups_pair_sum, K
        v = scores[idx]
        dups_pair_sum -= cnt[v] * (cnt[v] - 1) // 2
        cnt[v] -= 1
        dups_pair_sum += cnt[v] * (cnt[v] - 1) // 2
        K -= 1

    for L, R, i in queries:
        if L == -1:
            ans[i] = 0
            continue
        while curr_R < R:
            curr_R += 1
            add(curr_R)
        while curr_L > L:
            curr_L -= 1
            add(curr_L)
        while curr_R > R:
            remove(curr_R)
            curr_R -= 1
        while curr_L < L:
            remove(curr_L)
            curr_L += 1
        
        ans[i] = K * (K + 1) // 2 - dups_pair_sum

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

solve()

提出情報

ジャッジ結果