Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Segment Intersections: Manhattan Geometry

  For given $n$ segments which are parallel to X-axis or Y-axis, find the number of intersections of them.

Input

  In the first line, the number of segments $n$ is given. In the following $n$ lines, the $i$-th segment is given by coordinates of its end points in the following format:

$x_1 \; y_1 \; x_2 \; y_2$

The coordinates are given in integers.

Output

  Print the number of intersections in a line.

Constraints

$1 \leq n \leq 100,000$

$ -1,000,000,000 \leq x_1, y_1, x_2, y_2 \leq 1,000,000,000$

Two parallel segments never overlap or touch.

The number of intersections  $\leq 1,000,000$

Sample Input 1

6
2 2 2 5
1 3 5 3
4 1 4 4
5 2 7 2
6 1 6 3
6 5 6 7

Sample Output 1

3



Sample input:
6
2 2 2 5
1 3 5 3
4 1 4 4
5 2 7 2
6 1 6 3
6 5 6 7


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import collections
import math

import bisect

class Vector2(collections.namedtuple("Vector2", ["x",  "y"])):

    def __add__(self, other):
        return Vector2(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Vector2(self.x - other.x, self.y - other.y)

    def __mul__(self, scalar):
        return Vector2(self.x * scalar, self.y * scalar)

    def __neg__(self):
        return Vector2(-self.x, -self.y)

    def __pos__(self):
        return Vector2(+self.x, +self.y)

    def __abs__(self):  # norm
        return math.sqrt(float(self.x * self.x + self.y * self.y))

    def __truediv__(self, scalar):
        return Vector2(self.x / scalar, self.y / scalar)

    def abs2(self):
        return float(self.x * self.x + self.y * self.y)

    def dot(self, other):  # dot product
        return self.x * other.x + self.y * other.y

    def cross(self, other):  # cross product
        return self.x * other.y - self.y * other.x


def getDistanceSP(segment, point):
    p = point
    p1, p2 = segment
    if (p2 - p1).dot(p - p1) < 0:
        return abs(p - p1)
    if (p1 - p2).dot(p - p2) < 0:
        return abs(p - p2)
    return abs((p2 - p1).cross(p - p1)) / abs(p2 - p1)


def getDistance(s1, s2):
    a, b = s1
    c, d = s2
    if intersect(s1, s2):  # intersect
        return 0
    return min(getDistanceSP(s1, c), getDistanceSP(s1, d), getDistanceSP(s2, a), getDistanceSP(s2, b))


def ccw(p0, p1, p2):
    a = p1 - p0
    b = p2 - p0
    if a.cross(b) > 0:
        return 1  # COUNTER_CLOCKWISE
    elif a.cross(b) < 0:
        return -1  # CLOCKWISE
    elif a.dot(b) < 0:
        return 2  # ONLINE_BACK
    elif abs(a) < abs(b):
        return -2  # ONLINE_FRONT
    else:
        return 0  # ON_SEGMENT


def intersect(s1, s2):
    a, b = s1
    c, d = s2
    return ccw(a, b, c) * ccw(a, b, d) <= 0 and ccw(c, d, a) * ccw(c, d, b) <= 0


def project(l, p):
    p1, p2 = l
    base = p2 - p1
    hypo = p - p1
    return p1 + base * (hypo.dot(base) / abs(base)**2)


class Circle():
    def __init__(self, c, r):
        self.c = c
        self.r = r


def getCrossPoints(c, l):
    pr = project(l, c.c)
    p1, p2 = l
    e = (p2 - p1) / abs(p2 - p1)
    base = math.sqrt(c.r * c.r - (pr - c.c).abs2())
    return [pr + e * base, pr - e * base]


def polar(r, a):
    return Vector2(r * math.cos(a), r * math.sin(a))


def getCrossPointsCircle(c1, c2):
    base = c2.c - c1.c
    d = abs(base)
    a = math.acos((c1.r**2 + d**2 - c2.r**2) / (2 * c1.r * d))
    t = math.atan2(base.y, base.x)
    return [c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a)]


def contains(g, p):
    n = len(g)
    x = 0
    for i in range(n):
        a = g[i] - p
        b = g[(i + 1) % n] - p
        if a.cross(b) == 0 and a.dot(b) <= 0:
            return 1
        if a.y > b.y:
            a, b = b, a
        if a.y <= 0 and b.y > 0 and a.cross(b) > 0:
            x += 1

    if x % 2 == 1:
        return 2
    else:
        return 0


def andrewScan(s):
    u = []
    l = []
    s = sorted(s, key=lambda x: (x.x, x.y))
    if len(s) < 3:
        return s
    u.append(s[0])
    u.append(s[1])
    l.append(s[-1])
    l.append(s[-2])

    for i in range(2, len(s)):
        for n in range(len(u), 1, -1):
            if ccw(u[n - 2], u[n - 1], s[i]) != 1:
                break
            else:
                u.pop()
        u.append(s[i])

    for i in range(len(s) - 3, -1, -1):
        for n in range(len(l), 1, -1):
            if ccw(l[n - 2], l[n - 1], s[i]) != 1:
                break
            else:
                l.pop()
        l.append(s[i])

    ans = l + u[1:-1]
    ans.reverse()
    return ans

class EndPoint():
    def __init__(self, p, seg, st):
        self.p = p
        self.seg = seg
        self.st = st
    

if __name__ == '__main__':

    n = int(input())
    EP = []
    S = []
    for i in range(n):
        a, b, c, d = map(int, input().split())
        if a == c: # y軸と平行
            EP.append(EndPoint(Vector2(a, min(b, d)), i, 0)) # bottom
            EP.append(EndPoint(Vector2(a, max(b, d)), i, 3)) # top
            S.append([Vector2(a, max(b, d)), Vector2(a, min(b, d))])
        else: # x軸と平行
            EP.append(EndPoint(Vector2(min(a, c), b), i, 1)) # left
            EP.append(EndPoint(Vector2(max(a, c), b), i, 2)) # right
            S.append([Vector2(min(a, c), b), Vector2(max(a, c), b)])
    
    EP = sorted(EP, key=lambda x: (x.p.y, x.st))
    BT = []
    cnt = 0
    for e in EP:
        if e.st == 3: # top
            BT.remove(e.p.x)
        elif e.st == 0: # bottom
            bisect.insort_left(BT, e.p.x)
        elif e.st == 1: # left
            l = bisect.bisect_left(BT, S[e.seg][0].x)
            r = bisect.bisect_right(BT, S[e.seg][1].x)
            cnt += r-l

    print(cnt)

Submission status: Accepted

Solution code:
from enum import IntEnum


class Action(IntEnum):
    ADD = 1
    SEARCH = 2
    REMOVE = 3


class Color(IntEnum):
    BLACK = 0
    RED = 1

    @staticmethod
    def flip(c):
        return [Color.RED, Color.BLACK][c.value]


class Node:
    __slots__ = ('value', 'left', 'right', 'color', 'valid')

    def __init__(self, value):
        self.value = value
        self.left = Leaf
        self.right = Leaf
        self.color = Color.RED
        self.valid = True

    def flip_color(self):
        self.color = Color.flip(self.color)

    def is_red(self):
        return self.color == Color.RED

    def __str__(self):
        return ('(' + str(self.left) + ', '
                + str(self.value) + ', ' + str(self.right) + ')')


class LeafNode(Node):
    def __init__(self):
        self.value = None
        self.left = None
        self.right = None
        self.color = None
        self.valid = False

    def flip_color(self):
        pass

    def is_red(self):
        return False

    def __str__(self):
        return 'Leaf'


Leaf = LeafNode()


class RedBlackBST:
    def __init__(self):
        self.root = Leaf

    def add(self, value):
        def _add(node):
            if node is Leaf:
                node = Node(value)
            if node.value > value:
                node.left = _add(node.left)
            elif node.value < value:
                node.right = _add(node.right)
            else:
                if not node.valid:
                    node.valid = True

            node = self._balance(node)
            return node

        self.root = _add(self.root)
        self.root.color = Color.BLACK

    def _balance(self, node):
        if node.right.is_red() and not node.left.is_red():
            node = self._rotate_left(node)
        if node.left.is_red() and node.left.left.is_red():
            node = self._rotate_right(node)
        if node.left.is_red() and node.right.is_red():
            node = self._flip_colors(node)
        return node

    def _rotate_left(self, node):
        x = node.right
        node.right = x.left
        x.left = node
        x.color = node.color
        node.color = Color.RED
        return x

    def _rotate_right(self, node):
        x = node.left
        node.left = x.right
        x.right = node
        x.color = node.color
        node.color = Color.RED
        return x

    def _flip_colors(self, node):
        node.flip_color()
        node.left.flip_color()
        node.right.flip_color()
        return node

    def remove(self, value):
        def _remove(node):
            if node is Leaf:
                return
            if node.value > value:
                _remove(node.left)
            elif node.value < value:
                _remove(node.right)
            else:
                node.valid = False

        _remove(self.root)

    def count(self, min_, max_):
        def _range(node):
            if node is Leaf:
                return 0

            if node.value > max_:
                return _range(node.left)
            elif node.value < min_:
                return _range(node.right)
            else:
                count = _range(node.left) + _range(node.right)
                if node.valid:
                    count += 1
                return count

        return _range(self.root)

    def __str__(self):
        return str(self.root)


def count_intersections(segments):
    segments.sort()
    tree = RedBlackBST()
    count = 0
    for seg in segments:
        x, action, y = seg
        if action == Action.SEARCH:
            count += tree.count(*y)
        elif action == Action.ADD:
            tree.add(y)
        elif action == Action.REMOVE:
            tree.remove(y)

    return count


n=int(input())
segs=[]

for i in range(n):
  x1,y1,x2,y2=map(int,input().split())
  if x1>x2 or y1>y2:
    x1,x2=x2,x1
    y1,y2=y2,y1
  if x1==x2:
    segs.append((x1,Action.SEARCH,(y1,y2)))
  else:
    segs.append((x1,Action.ADD,y1))
    segs.append((x2,Action.REMOVE,y2))
print(count_intersections(segs))

Submission status: Accepted

Solution code:
#線分交差問題

import bisect

class BIT:
    def __init__(self, n):
        self.tree = [0]*(n+1)
        self.n = n
    
    def add(self, i, v):
        while i <= self.n:
            self.tree[i] += v
            i += i & -i
        
    
    def _sum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i -= i & -i
        return ret
    
    def sum(self, l, h):
        return self._sum(h) - self._sum(l-1)
    
n = int(input())
vx = []
xs = set()
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        vx.append((y1, float('-inf'),x1))
        vx.append((y2, float('inf'),x2))
        xs.add(x1)
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        vx.append((y1, x1, x2))
vx.sort()

bit = BIT(len(xs))
xs = [float('-inf')] + sorted(xs)
ix = {v: i for i, v in enumerate(xs)}
ans = 0

for y, j, x2 in vx:
    if j == float('-inf'):
        bit.add(ix[x2],1)
    elif j == float('inf'):
        bit.add(ix[x2], -1)
    else:
        l = bisect.bisect_left(xs, j)
        r = bisect.bisect(xs, x2) - 1
        ans += bit.sum(l, r)
        
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from operator import itemgetter
readline = stdin.readline


#readline = open('???.txt').readline

VERTICAL_LOW, HORIZONTAL, VERTICAL_HIGH = 0, 1, 2

import math
class segment_tree:
    
    # self.table is 1-indexed
    # math.log2 not implemented 3.2.3
    def __init__(self, size):
        self.offset = 2 ** math.ceil(math.log(size, 2))
        self.table = [0] * self.offset * 2
        for i in reversed(range(1, self.offset)):
            self.table[i] = self.table[2 * i] + self.table[2 * i + 1]

    # [l, r] closed-interval
    def sum(self, l, r):
        return sum(self.__range(l,r))

    def __range(self, l, r):
        l += self.offset
        r += self.offset
        while l <= r:
            if l & 1:
                yield self.table[l]
                l += 1
            l >>= 1
            if r & 1 == 0:
                yield self.table[r]
                r -= 1
            r >>= 1
        
    def add(self, i, x):
        i += self.offset
        self.table[i] += x
        while 1 < i:
            i >>= 1
            self.table[i] = self.table[2 * i] + self.table[2 * i + 1]

def main():
    n = int(readline())
    p = [list(map(int, readline().split())) for _ in range(n)]
    x = set(x1 for x1, y1, x2, y2 in p) | set(x2 for x1, y1, x2, y2 in p)
    c = {xi:i for i, xi in enumerate(sorted(x))}
    que = []
    for x1, y1, x2, y2 in p:
        if y1 == y2:
            if x1 > x2:
                x1, x2 = x2, x1
            que.append((y1, HORIZONTAL, c[x1], c[x2]))
        else:
            if y1 > y2:
                y1, y2 = y2, y1
            x1 = c[x1]
            que.append((y1, VERTICAL_LOW, x1, None))
            que.append((y2, VERTICAL_HIGH, x1, None))
    que.sort(key=itemgetter(0, 1))

    vertical_info = segment_tree(len(x))

    intersection = 0
    for y1, action, x1, x2 in que:
        if action == VERTICAL_LOW:
            vertical_info.add(x1, 1)
        elif action == HORIZONTAL:
            intersection += vertical_info.sum(x1, x2)
        else:
            vertical_info.add(x1, -1)
    print(intersection)
main()

Submission status: Accepted

Solution code:
from bisect import bisect
n = input()

data = [0]*(n+1)
def get(i):
    r = 0
    while i>0:
        r += data[i]
        i -= i & -i
    return r
def add(i, x):
    while i <= n:
        data[i] += x
        i += i & -i

H = []
V = []
s = set()
for i in xrange(n):
    x1, y1, x2, y2 = map(int, raw_input().split())
    if x1 == x2:
        if y1 > y2: y1, y2 = y2, y1
        V.append((x1, y1, y2))
    else:
        if x1 > x2: x1, x2 = x2, x1
        H.append((x1, y1, 1))
        H.append((x2+1, y1, -1))
        s.add(y1)
ys = [-10**18] + sorted(s)
ymap = {e: i for i, e in enumerate(ys)}.__getitem__
V.sort(); H.sort()

ans = 0
idx_h = 0; hn = len(H)
for x, y1, y2 in V:
    while idx_h < hn and H[idx_h][0] <= x:
        add(ymap(H[idx_h][1]), H[idx_h][2])
        idx_h += 1
    idx_l = bisect(ys, y1-1)-1
    idx_r = bisect(ys, y2)-1
    ans += get(idx_r) - get(idx_l)
print ans

Submission status: Accepted

Solution code:
# Acceptance of input
import sys

file_input = sys.stdin

n = file_input.readline()

EP = []

for line in file_input:
    x1, y1, x2, y2 = (map(int, line.split()))
    # point[2] corresponds to the position of the end point.
    # 1 is left, 2 is lower, 3 is upper and 4 is right.
    if y1 < y2:
        p1 = (x1, y1, 2)
        p2 = (x2, y2, 3)
    elif y1 > y2:
        p1 = (x1, y1, 3)
        p2 = (x2, y2, 2)
    elif x1 < x2:
        p1 = (x1, y1, 1)
        p2 = (x2, y2, 4)
    else:
        p1 = (x1, y1, 4)
        p2 = (x2, y2, 1)
    EP += [p1, p2]

# Sweep function
import bisect

def manhattan_intersection(point_list):
    point_list.sort(key = lambda p: (p[1], p[0], p[2]))
    T = []
    cnt = 0
    flag = False
    for p in point_list:
        position = p[2]
        if position == 3:
            i = bisect.bisect_left(T, p[0])
            T.pop(i)
            if flag:
                cnt += 1
        elif position == 2:
            bisect.insort(T, p[0])
        elif position == 4:
            cnt += bisect.bisect(T, p[0]) - left_end
            flag = False
        else:
            left_end = bisect.bisect_left(T, p[0])
            flag = True
    print(cnt)

# Output
manhattan_intersection(EP)

Submission status: Accepted

Solution code:
# Acceptance of input
import sys

file_input = sys.stdin

n = file_input.readline()

EP = []
l = -1000000001
r = 1000000001

for line in file_input:
    x1, y1, x2, y2 = (map(int, line.split()))
    if y1 == y2:
        EP.append((min(x1, x2), l, y1))
        EP.append((max(x1, x2), r, y1))
    else:
        EP.append((x1, min(y1, y2), max(y1, y2)))

# Sweep
import bisect

EP.sort()
BT = []
cnt = 0

for p in EP:
    y1 = p[1]
    if y1 == l:
        bisect.insort(BT, p[2])
    elif y1 == r:
        i = bisect.bisect_left(BT, p[2])
        BT.pop(i)
    else:
        cnt += bisect.bisect(BT, p[2]) - bisect.bisect_left(BT, y1)

# Output
print(cnt)

Submission status: Accepted

Solution code:
# Acceptance of input
import sys

file_input = sys.stdin

n = file_input.readline()

EP = []
l = -1000000001
u = 1000000001

for line in file_input:
    x1, y1, x2, y2 = (map(int, line.split()))
    if x1 == x2:
        if y1 < y2:
            EP.append((y1, l, x1))
            EP.append((y2, u, x1))
        else:
            EP.append((y1, u, x1))
            EP.append((y2, l, x1))
    else:
        if x1 < x2:
            EP.append((y1, x1, x2))
        else:
            EP.append((y1, x2, x1))

# Sweep
import bisect

EP.sort()
BT = []
cnt = 0

for p in EP:
    x1 = p[1]
    if x1 == l:
        bisect.insort(BT, p[2])
    elif x1 == u:
        i = bisect.bisect_left(BT, p[2])
        BT.pop(i)
    else:
        cnt += bisect.bisect(BT, p[2]) - bisect.bisect_left(BT, x1)

# Output
print(cnt)

Submission status: Accepted

Solution code:
# Acceptance of input
import sys

file_input = sys.stdin

n = file_input.readline()

EP = []
l = -1000000001
u = 1000000001

for line in file_input:
    x1, y1, x2, y2 = (map(int, line.split()))
    if x1 == x2:
        if y1 < y2:
            EP.append((y1, l, x1))
            EP.append((y2, u, x1))
        else:
            EP.append((y1, u, x1))
            EP.append((y2, l, x1))
    else:
        if x1 < x2:
            EP.append((y1, x1, x2))
        else:
            EP.append((y1, x2, x1))

# Sweep
import bisect

EP.sort()
BT = []
cnt = 0

for p in EP:
    e = p[1]
    if e == l:
        bisect.insort(BT, p[2])
    elif e == u:
        i = bisect.bisect_left(BT, p[2])
        BT.pop(i)
    else:
        cnt += bisect.bisect(BT, p[2]) - bisect.bisect_left(BT, e)

# Output
print(cnt)

Submission status: Accepted

Solution code:
# Acceptance of input
import sys

file_input = sys.stdin

n = file_input.readline()

EP = []
l = -1000000001
u = 1000000001
vs_x = set()

for line in file_input:
    x1, y1, x2, y2 = (map(int, line.split()))
    if x1 == x2:
        if y1 < y2:
            EP.append((y1, l, x1))
            EP.append((y2, u, x1))
        else:
            EP.append((y1, u, x1))
            EP.append((y2, l, x1))
        vs_x.add(x1)
    else:
        if x1 < x2:
            EP.append((y1, x1, x2))
        else:
            EP.append((y1, x2, x1))

vs_x = sorted(vs_x)

# Segment Tree(Range Sum Query)
import math

m = 2 ** math.ceil(math.log(len(vs_x), 2))
ST = [0] * (2 * m - 1)

def switch(i):
    i += m - 1
    if ST[i]:
        d = -1
    else:
        d = 1
    ST[i] += d

    while i > 0:
        i = (i - 1) // 2
        ST[i] += d

def get_sum(s, t, k, l, r):
    if r < s or t < l:
        return 0
    elif s <= l and r <= t:
        return ST[k]
    else:
        mid = (l + r) // 2
        l_sum = get_sum(s, t, k * 2 + 1, l, mid)
        r_sum = get_sum(s, t, k * 2 + 2, mid + 1, r)
        return l_sum + r_sum

# Sweep
import bisect

EP.sort()
cnt = 0

for p in EP:
    e = p[1]
    if e == l or e == u:
        vs_i = bisect.bisect_left(vs_x, p[2])
        switch(vs_i)
    else:
        l_x = bisect.bisect_left(vs_x, e)
        r_x = bisect.bisect(vs_x, p[2]) - 1
        cnt += get_sum(l_x, r_x, 0, 0, m - 1)

# Output
print(cnt)

Submission status: Accepted

Solution code:
# Acceptance of input
import sys

file_input = sys.stdin

n = file_input.readline()

EP = []
l = -1000000001
u = 1000000001
vs_x = set()

for line in file_input:
    x1, y1, x2, y2 = (map(int, line.split()))
    if x1 == x2:
        if y1 < y2:
            EP.append((y1, l, x1))
            EP.append((y2, u, x1))
        else:
            EP.append((y1, u, x1))
            EP.append((y2, l, x1))
        vs_x.add(x1)
    else:
        if x1 < x2:
            EP.append((y1, x1, x2))
        else:
            EP.append((y1, x2, x1))

vs_x = sorted(vs_x)

# Binary Indexed Tree
class BinaryIndexedTree:
    def __init__(self, n):
        self.data = [0] * (n + 1)
        self.num = n

    def switch(self, i, d):
        while  i <= self.num:
            self.data[i] += d
            i += i & -i

    def _sum(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= i & -i
        return s

    def seg_sum(self, a, b):
        return self._sum(b) - self._sum(a - 1)

# Sweep
import bisect

EP.sort()
BIT = BinaryIndexedTree(len(vs_x))
cnt = 0

for p in EP:
    e = p[1]
    if e == l:
        vx = bisect.bisect(vs_x, p[2])
        BIT.switch(vx, 1)
    elif e == u:
        vx = bisect.bisect(vs_x, p[2])
        BIT.switch(vx, -1)
    else:
        l_x = bisect.bisect_left(vs_x, e) + 1
        r_x = bisect.bisect(vs_x, p[2])
        cnt += BIT.seg_sum(l_x, r_x)

# Output
print(cnt)

Submission status: Accepted

Solution code:
# Acceptance of input
import sys

file_input = sys.stdin

n = file_input.readline()

EP = []
l = -1000000001
u = 1000000001
vs_x = set()

for line in file_input:
    x1, y1, x2, y2 = (map(int, line.split()))
    if x1 == x2:
        if y1 < y2:
            EP.append((y1, l, x1))
            EP.append((y2, u, x1))
        else:
            EP.append((y1, u, x1))
            EP.append((y2, l, x1))
        vs_x.add(x1)
    else:
        if x1 < x2:
            EP.append((y1, x1, x2))
        else:
            EP.append((y1, x2, x1))

# Binary Indexed Tree
class BinaryIndexedTree:
    def __init__(self, n):
        self.data = [0] * (n + 1)
        self.num = n

    def switch(self, i, d):
        while  i <= self.num:
            self.data[i] += d
            i += i & -i

    def _sum(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= i & -i
        return s

    def seg_sum(self, a, b):
        return self._sum(b) - self._sum(a - 1)

# Sweep
import bisect

EP.sort()
BIT = BinaryIndexedTree(len(vs_x))
vs_x = [l] + sorted(vs_x)
d_vs_x = {e: i for i, e in enumerate(vs_x)}
cnt = 0

for p in EP:
    e = p[1]
    if e == l:
        BIT.switch(d_vs_x[p[2]], 1)
    elif e == u:
        BIT.switch(d_vs_x[p[2]], -1)
    else:
        l_x = bisect.bisect_left(vs_x, e)
        r_x = bisect.bisect(vs_x, p[2]) - 1
        cnt += BIT.seg_sum(l_x, r_x)

# Output
print(cnt)

Submission status: Accepted

Solution code:
# Acceptance of input
import sys

file_input = sys.stdin

n = file_input.readline()

EP = []
l = -1000000001
u = 1000000001
vs_x = set()
h_num = 0

for line in file_input:
    x1, y1, x2, y2 = (map(int, line.split()))
    if x1 == x2:
        if y1 < y2:
            EP.append((y1, l, x1))
            EP.append((y2, u, x1))
        else:
            EP.append((y1, u, x1))
            EP.append((y2, l, x1))
        vs_x.add(x1)
    else:
        if x1 < x2:
            EP.append((y1, x1, x2))
        else:
            EP.append((y1, x2, x1))
        h_num += 1

# Binary Indexed Tree
class BinaryIndexedTree:
    def __init__(self, n):
        self.data = [0] * (n + 1)
        self.num = n

    def switch(self, i, d):
        while  i <= self.num:
            self.data[i] += d
            i += i & -i

    def _sum(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= i & -i
        return s

    def seg_sum(self, a, b):
        return self._sum(b) - self._sum(a - 1)

# Sweep
import bisect

EP.sort()
BIT = BinaryIndexedTree(len(vs_x))
vs_x = [l] + sorted(vs_x)
d_vs_x = {e: i for i, e in enumerate(vs_x)}
cnt = 0

for p in EP:
    e = p[1]
    if e == l:
        BIT.switch(d_vs_x[p[2]], 1)
    elif e == u:
        BIT.switch(d_vs_x[p[2]], -1)
    else:
        l_x = bisect.bisect_left(vs_x, e)
        r_x = bisect.bisect(vs_x, p[2]) - 1
        cnt += BIT.seg_sum(l_x, r_x)
        h_num -= 1
    if h_num == 0:
        break

# Output
print(cnt)

Submission status: Accepted

Solution code:
import bisect


def memoize(f):
    cache = {}

    def func(x):
        if x not in cache:
            cache[x] = f(x)
        return cache[x]

    return func


@memoize
def get_bisect(y):
    return bisect.bisect(vy, (y,))


n = int(input())
vx, vy = [], []
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        vx.append((x1, y1, y2))
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        vy.append((y1, x1, x2))
vy.sort()

ans = 0

for x, y1, y2 in vx:
    it1, it2 = get_bisect(y1), get_bisect(y2 + 1)
    ans += sum(1 for y, x1, x2 in vy[it1:it2] if x1 <= x <= x2)

print(ans)

Submission status: Accepted

Solution code:
import bisect


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

    def add(self, i, v):
        while i <= self.n:
            self.tree[i] += v
            i += i & -i

    def _sum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i -= i & -i
        return ret

    def sum(self, l, h):
        return self._sum(h) - self._sum(l - 1)


n = int(input())
vx = []
xs = set()
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        vx.append((y1, float('-inf'), x1))
        vx.append((y2, float('inf'), x1))
        xs.add(x1)
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        vx.append((y1, x1, x2))
vx.sort()

bit = BIT(len(xs))
xs = [float('-inf')] + sorted(xs)
ix = {v: i for i, v in enumerate(xs)}
ans = 0

for y, j, x2 in vx:
    if j == float('-inf'):
        bit.add(ix[x2], 1)
    elif j == float('inf'):
        bit.add(ix[x2], -1)
    else:
        i1 = bisect.bisect_left(xs, j)
        i2 = bisect.bisect(xs, x2) - 1
        ans += bit.sum(i1, i2)

print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
readline = sys.stdin.readline
n = int(readline())
EP = []
l = -1000000001
u = 1000000001
vs_x = set()
h_num = 0
for _ in [0] * n:
    x1, y1, x2, y2 = (map(int, readline().split()))
    if x1 == x2:
        if y1 < y2:
            EP.append((y1, l, x1))
            EP.append((y2, u, x1))
        else:
            EP.append((y1, u, x1))
            EP.append((y2, l, x1))
        vs_x.add(x1)
    else:
        if x1 < x2:
            EP.append((y1, x1, x2))
        else:
            EP.append((y1, x2, x1))
        h_num += 1
class BinaryIndexedTree:
    __slots__ = ('data', 'num')
    def __init__(self, n):
        self.data = [0] * (n + 1)
        self.num = n
    def switch(self, i, d):
        while i <= self.num:
            self.data[i] += d
            i += i & -i
    def _sum(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= i & -i
        return s
    def seg_sum(self, a, b):
        return self._sum(b) - self._sum(a - 1)
EP.sort()
BIT = BinaryIndexedTree(len(vs_x))
vs_x = [l] + sorted(vs_x)
d_vs_x = {e: i for i, e in enumerate(vs_x)}
cnt = 0
for p in EP:
    e = p[1]
    if e == l:
        BIT.switch(d_vs_x[p[2]], 1)
    elif e == u:
        BIT.switch(d_vs_x[p[2]], -1)
    else:
        l_x = bisect.bisect_left(vs_x, e)
        r_x = bisect.bisect(vs_x, p[2]) - 1
        cnt += BIT.seg_sum(l_x, r_x)
        h_num -= 1
    if h_num == 0: break
print(cnt)