Line Intersections

input/code.cpp: In function 'int main()':
input/code.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i=0; i < x_coords.size(); ++i){
      |                  ~~^~~~~~~~~~~~~~~~~

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

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

    BIT(int n) : size(n), tree(n + 2, 0) {}

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

    // Query the prefix sum up to idx
    int query(int idx) const {
        int res = 0;
        int i = idx;
        while (i > 0) {
            res += tree[i];
            i -= i & (-i);
        }
        return res;
    }

    // Query the range sum from l to r
    int range_query(int l, int r) const {
        return query(r) - query(l - 1);
    }
};

// Event structure
struct Event {
    int y;      // y-coordinate of the event
    int type;   // 0 = add, 1 = query, 2 = remove
    int x1;     // For add/remove: x-coordinate; For query: left x
    int x2;     // For query: right x; unused otherwise

    bool operator<(const Event& other) const {
        if (y != other.y)
            return y < other.y;
        return type < other.type; // add < query < remove
    }
};

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

    int n;
    cin >> n;

    vector<tuple<int, int, int, int>> lines(n);
    for(auto &line : lines){
        cin >> get<0>(line) >> get<1>(line) >> get<2>(line) >> get<3>(line);
    }

    vector<tuple<int, int, int>> h_lines; // horizontal lines: y, x1, x2
    vector<tuple<int, int, int>> v_lines; // vertical lines: x, y1, y2
    vector<int> x_coords;

    for(auto &line : lines){
        int x1 = get<0>(line);
        int y1 = get<1>(line);
        int x2 = get<2>(line);
        int y2 = get<3>(line);

        if(y1 == y2){
            // Horizontal line
            if(x1 > x2) swap(x1, x2);
            h_lines.emplace_back(y1, x1, x2);
            x_coords.push_back(x1);
            x_coords.push_back(x2);
        }
        else if(x1 == x2){
            // Vertical line
            if(y1 > y2) swap(y1, y2);
            v_lines.emplace_back(x1, y1, y2);
            x_coords.push_back(x1);
        }
        // According to problem statement, all lines are either horizontal or vertical
    }

    // Coordinate Compression
    sort(x_coords.begin(), x_coords.end());
    x_coords.erase(unique(x_coords.begin(), x_coords.end()), x_coords.end());
    unordered_map<int, int> x_to_idx;
    for(int i=0; i < x_coords.size(); ++i){
        x_to_idx[x_coords[i]] = i+1; // 1-based indexing for BIT
    }
    int m = x_coords.size();

    // Create events
    vector<Event> events;
    for(auto &v : v_lines){
        int x = get<0>(v);
        int y1 = get<1>(v);
        int y2 = get<2>(v);
        int x_c = x_to_idx[x];
        events.push_back(Event{y1, 0, x_c, 0}); // add
        events.push_back(Event{y2 + 1, 2, x_c, 0}); // remove
    }
    for(auto &h : h_lines){
        int y = get<0>(h);
        int x1 = get<1>(h);
        int x2 = get<2>(h);
        int x1_c = x_to_idx[x1];
        int x2_c = x_to_idx[x2];
        events.push_back(Event{y, 1, x1_c, x2_c}); // query
    }

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

    // Initialize BIT
    BIT bit(m);

    long long total = 0;
    for(auto &event : events){
        if(event.type == 0){
            // Add vertical line
            bit.update(event.x1, 1);
        }
        else if(event.type == 2){
            // Remove vertical line
            bit.update(event.x1, -1);
        }
        else{
            // Query horizontal line
            int cnt = bit.range_query(event.x1, event.x2);
            total += cnt;
        }
    }

    cout << total;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

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