Line Intersections

#include <bits/stdc++.h>

using namespace std;

void bitree_add(long long bitree[], int n, int index, long long value) {

    index = index + 1;

    while (index <= n) {
        bitree[index] += value;
        index += index & -index;
    }

}

long long *bitree_create(int input[], int n) {

    long long *output = new long long[n+1];
    for (int i = 1; i <= n; i++)
        output[i] = 0;
    
    for (int i = 0; i < n; i++)
        bitree_add(output, n, i, input[i]);
    
    return output;

}

long long bitree_sum(long long bitree[], int index) {
    index = index + 1;
    long long sum = 0;

    while (index >= 1) {
        sum += bitree[index];
        index -= index & -index;
    }
    
    return sum;
}

long long bitree_sum(long long bitree[], int a, int b) {
    return bitree_sum(bitree, b) - bitree_sum(bitree, a-1);
}

struct Point {
    int x, y;
};

struct Vertical {
    int x, ymin, ymax;
};

struct Event {
    int kind;
    union {
        Point point;
        Vertical vertical;
    } get;

    bool operator<(const Event& e) const {
        if (kind == 3) {
            if (e.kind == 3)
                return get.vertical.x < e.get.vertical.x;
            return get.vertical.x < e.get.point.x;
        } else {
            if (e.kind == 3)
                return get.point.x < e.get.vertical.x;
            return get.point.x < e.get.point.x;
        }
    }
};

int main() {

    int n;
    cin >> n;

    vector<Event> events;

    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        if (x1 == x2) {
            Vertical vertical = { x1, min(y1, y2), max(y1, y2) };
            Event event;
            event.kind = 3;
            event.get.vertical = vertical;
            events.push_back(event);
        } else {
            Point p1, p2;

            if (x1 < x2) {
                p1 = { x1, y1 };
                p2 = { x2, y2 };
            } else {
                p1 = { x2, y2 };
                p2 = { x1, y1 };
            }

            Event e1;
            e1.kind = 1;
            e1.get.point = p1;
            events.push_back(e1);

            Event e2;
            e2.kind = 2;
            e2.get.point = p2;
            events.push_back(e2);
        }
    }

    sort(events.begin(), events.end());

    constexpr int m = (10e5 * 2 + 1);
    int input[m];
    for (int i = 0; i < m; i++)
        input[i] = 0;

    long long *bitree = bitree_create(input, m);

    //multiset<int> active_y;
    long long output = 0;

    for (Event &e : events) {

        if (e.kind == 1) {
            bitree_add(bitree, m, e.get.point.y + 10e5, 1);
        } else if (e.kind == 2) {
            bitree_add(bitree, m, e.get.point.y + 10e5, -1);
        } else {
            output += bitree_sum(bitree, e.get.vertical.ymin + 10e5, e.get.vertical.ymax + 10e5);
            /*
            for (auto i = active_y.begin(); i != active_y.end(); i++) {
                int y = (*i);
                if (y >= e.get.vertical.ymin && y <= e.get.vertical.ymax)
                    output++;
            }
            */
        }

    }

    cout << output << endl;

}

/*
6
0 2 3 2
1 3 6 3
4 2 9 2
2 5 2 0
5 4 5 1
7 4 7 0

output: 5
*/

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