Line Intersections

from bisect import bisect_left, bisect_right
from collections import defaultdict

class BIT:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def add(self, index, value):
        while index <= self.size:
            self.tree[index] += value
            index += index & -index

    def sum(self, index):
        result = 0
        while index > 0:
            result += self.tree[index]
            index -= index & -index
        return result

    def range_sum(self, left, right):
        return self.sum(right) - self.sum(left - 1)

def compress_coordinates(coordinates):
    sorted_unique = sorted(set(coordinates))
    mapping = {val: i + 1 for i, val in enumerate(sorted_unique)}
    return mapping, len(sorted_unique)

def count_intersections(segments):
    horizontal = []
    vertical = []
    y_coords = []

    for x1, y1, x2, y2 in segments:
        if y1 == y2:  # Horizontal segment
            horizontal.append((x1, x2, y1))
            y_coords.append(y1)
        elif x1 == x2:  # Vertical segment
            vertical.append((x1, y1, y2))
            y_coords.extend([y1, y2])

    y_compressed, y_size = compress_coordinates(y_coords)
    bit = BIT(y_size)
    events = []

    for x1, x2, y in horizontal:
        y_c = y_compressed[y]
        events.append((x1, 'start', y_c))
        events.append((x2, 'end', y_c))

    for x, y1, y2 in vertical:
        y1_c = y_compressed[y1]
        y2_c = y_compressed[y2]
        events.append((x, 'query', y1_c, y2_c))

    events.sort()
    intersections = 0

    for event in events:
        if event[1] == 'start':
            bit.add(event[2], 1)
        elif event[1] == 'end':
            bit.add(event[2], -1)
        elif event[1] == 'query':
            _, _, y1_c, y2_c = event
            intersections += bit.range_sum(y1_c, y2_c)

    return intersections

n = int(input())
segments = [tuple(map(int, input().split())) for _ in range(n)]
print(count_intersections(segments))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: ACCEPTED

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: ACCEPTED

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: ACCEPTED

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: WRONG ANSWER

Test 25

Verdict: WRONG ANSWER

Test 26

Verdict: WRONG ANSWER

Test 27

Verdict: WRONG ANSWER

Test 28

Verdict: WRONG ANSWER

Test 29

Verdict: WRONG ANSWER

Test 30

Verdict: WRONG ANSWER

Test 31

Verdict: WRONG ANSWER

Test 32

Verdict: WRONG ANSWER

Test 33

Verdict: WRONG ANSWER

Test 34

Verdict: WRONG ANSWER

Test 35

Verdict: WRONG ANSWER

Test 36

Verdict: WRONG ANSWER

Test 37

Verdict: WRONG ANSWER

Test 38

Verdict: WRONG ANSWER

Test 39

Verdict: WRONG ANSWER

Test 40

Verdict: WRONG ANSWER