Line Intersections

input/code.cpp: In function 'int countIntersections(const std::vector<std::tuple<int, int, int, int> >&)':
input/code.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 0; i < yCoords.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

class FenwickTree {
public:
    FenwickTree(int size) : tree(size + 1, 0), size(size) {}
    void add(int idx, int value) {
        while (idx <= size) {
            tree[idx] += value;
            idx += idx & -idx;
        }
    }

    int sum(int idx) const {
        int result = 0;
        while (idx > 0) {
            result += tree[idx];
            idx -= idx & -idx;
        }
        return result;
    }

    int rangeSum(int left, int right) const {
        return sum(right) - sum(left - 1);
    }

private:
    vector<int> tree;
    int size;
};

struct Event {
    int x;
    int type;
    int y1, y2;

    bool operator<(const Event &other) const {
        if (x != other.x) return x < other.x;
        return type < other.type;
    }
};

int countIntersections(const vector<tuple<int, int, int, int>> &segments) {
    vector<Event> events;
    vector<int> yCoords;

    for (const auto &[x1, y1, x2, y2] : segments) {
        if (y1 == y2) {
            events.push_back({x1, 1, y1, y1});
            events.push_back({x2, -1, y1, y1});
            yCoords.push_back(y1);
        } else if (x1 == x2) {
            events.push_back({x1, 0, y1, y2});
            yCoords.push_back(y1);
            yCoords.push_back(y2);
        }
    }

    sort(yCoords.begin(), yCoords.end());
    yCoords.erase(unique(yCoords.begin(), yCoords.end()), yCoords.end());
    map<int, int> yCompressed;
    for (int i = 0; i < yCoords.size(); ++i) {
        yCompressed[yCoords[i]] = i + 1;
    }

    int ySize = yCoords.size();
    FenwickTree fenwick(ySize);

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

    int intersections = 0;
    for (const auto &event : events) {
        if (event.type == 1) {
            fenwick.add(yCompressed[event.y1], 1);
        } else if (event.type == -1) {
            fenwick.add(yCompressed[event.y1], -1);
        } else if (event.type == 0) {
            int y1_c = yCompressed[event.y1];
            int y2_c = yCompressed[event.y2];
            intersections += fenwick.rangeSum(min(y1_c, y2_c), max(y1_c, y2_c));
        }
    }

    return intersections;
}

int main() {
    int n;
    cin >> n;
    vector<tuple<int, int, int, int>> segments(n);

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

    cout << countIntersections(segments) << endl;
    return 0;
}

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