Line Intersections

#include <bits/stdc++.h>
using namespace std;

// Structure to represent a horizontal line
struct HorizontalLine {
    int y;
    int x_start;
    int x_end;
};

// Structure to represent a vertical line
struct VerticalLine {
    int x;
    int y_start;
    int y_end;
};

// Structure to represent an event
struct Event {
    int x;
    int type; // 0: add, 1: query, 2: remove
    int y; // For add and remove
    int y_start; // For query
    int y_end;   // For query

    // Comparator for sorting events
    bool operator<(const Event& other) const {
        if (x != other.x)
            return x < other.x;
        return type < other.type; // add < query < remove
    }
};

// Binary Indexed Tree (Fenwick Tree) implementation
struct FenwickTree {
    int size;
    vector<int> tree;

    FenwickTree(int n) : size(n), tree(n + 1, 0) {}

    void update(int index, int delta){
        while(index <= size){
            tree[index] += delta;
            index += index & (-index);
        }
    }

    int query(int index) const {
        int res = 0;
        int i = index;
        while(i > 0){
            res += tree[i];
            i -= i & (-i);
        }
        return res;
    }

    int query_range(int l, int r) const {
        if(l > r) return 0;
        return query(r) - query(l - 1);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<HorizontalLine> horizontal_lines;
    vector<VerticalLine> vertical_lines;
    vector<int> unique_y;

    for(int i=0; i<n; i++){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(y1 == y2){
            // Horizontal line
            int y = y1;
            int x_start = min(x1, x2);
            int x_end = max(x1, x2);
            horizontal_lines.push_back(HorizontalLine{y, x_start, x_end});
            unique_y.push_back(y);
        }
        else if(x1 == x2){
            // Vertical line
            int x = x1;
            int y_start = min(y1, y2);
            int y_end = max(y1, y2);
            vertical_lines.push_back(VerticalLine{x, y_start, y_end});
        }
        // According to problem statement, lines are either horizontal or vertical
    }

    // Coordinate compression for y's
    sort(unique_y.begin(), unique_y.end());
    unique_y.erase(unique(unique_y.begin(), unique_y.end()), unique_y.end());

    // Mapping y to index
    // y_map[y] = index
    // Not needed as we can use lower_bound on unique_y
    int m = unique_y.size();

    // Create events
    vector<Event> events;

    for(auto &h_line : horizontal_lines){
        // Add event
        events.push_back(Event{h_line.x_start, 0, h_line.y, 0, 0});
        // Remove event
        events.push_back(Event{h_line.x_end, 2, h_line.y, 0, 0});
    }

    for(auto &v_line : vertical_lines){
        // Query event
        events.push_back(Event{v_line.x, 1, 0, v_line.y_start, v_line.y_end});
    }

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

    // Initialize Fenwick Tree
    FenwickTree BIT(m);

    long long total_intersections = 0;

    for(auto &event : events){
        if(event.type == 0){
            // Add event
            // Find the index of y
            int y = event.y;
            int idx = lower_bound(unique_y.begin(), unique_y.end(), y) - unique_y.begin() + 1;
            BIT.update(idx, 1);
        }
        else if(event.type == 2){
            // Remove event
            int y = event.y;
            int idx = lower_bound(unique_y.begin(), unique_y.end(), y) - unique_y.begin() + 1;
            BIT.update(idx, -1);
        }
        else{
            // Query event
            int y_start = event.y_start;
            int y_end = event.y_end;
            // Find left index: first y >= y_start
            int left = lower_bound(unique_y.begin(), unique_y.end(), y_start) - unique_y.begin() + 1;
            // Find right index: last y <= y_end
            int right = upper_bound(unique_y.begin(), unique_y.end(), y_end) - unique_y.begin();
            // Query the number of y's in [y_start, y_end]
            total_intersections += BIT.query_range(left, right);
        }
    }

    cout << total_intersections;
}

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