Submission #76658607

---

Source Code Expand

n, d = map(int, input().split())
events = []

for _ in range(n):
    s, t = map(int, input().split())
    l = s
    r = t - d
    
    if l <= r:
        events.append((l, 1))
        events.append((r + 1, -1))
        
events.sort()

ans = 0
cur_c = 0
i = 0
events_num = len(events)

while i < events_num:
    j = i
    while j < events_num and events[j][0] == events[i][0]:
        cur_c += events[j][1]
        j += 1
        
    if j < events_num:
        length = events[j][0] - events[i][0]
        if cur_c >= 2:
            pairs = cur_c * (cur_c - 1) // 2
            ans += length * pairs
            
    i = j
    
print(ans)

Submission Info

Judge Result