Line Intersections

input/code.cpp: In function 'int main()':
input/code.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
input/code.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cstdio>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector<tuple<int, int, int>> horizontal_lines; // (x_start, x_end, y)
    vector<tuple<int, int, int>> vertical_lines;   // (x, y_start, y_end)
    set<int> y_coords;

    for (int i = 0; i < n; ++i) {
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

        if (y1 == y2) {
            // Horizontal line
            int y0 = y1;
            int x_start = min(x1, x2);
            int x_end = max(x1, x2);
            horizontal_lines.push_back(make_tuple(x_start, x_end, y0));
            y_coords.insert(y0);
        } else if (x1 == x2) {
            // Vertical line
            int x0 = x1;
            int y_start = min(y1, y2);
            int y_end = max(y1, y2);
            vertical_lines.push_back(make_tuple(x0, y_start, y_end));
            y_coords.insert(y_start);
            y_coords.insert(y_end);
        }
    }

    // Coordinate compression
    vector<int> y_list(y_coords.begin(), y_coords.end());
    sort(y_list.begin(), y_list.end());
    map<int, int> y_index;
    int idx = 1;
    for (int y : y_list) {
        y_index[y] = idx++;
    }
    int M = y_list.size();

    // Events: (x, event_type, y1) for add/remove events
    // Events: (x, event_type, y1, y2) for query events
    struct Event {
        int x;
        int type; // 0 = add, 1 = query, 2 = remove
        int y1;
        int y2;
        Event(int x_, int type_, int y1_, int y2_ = 0) : x(x_), type(type_), y1(y1_), y2(y2_) {}
    };
    vector<Event> events;

    // Add events for horizontal lines
    for (auto &hl : horizontal_lines) {
        int x_start, x_end, y0;
        tie(x_start, x_end, y0) = hl;
        int idx_y = y_index[y0];
        events.emplace_back(x_start, 0, idx_y); // Add event
        events.emplace_back(x_end, 2, idx_y);   // Remove event
    }

    // Add events for vertical lines
    for (auto &vl : vertical_lines) {
        int x0, y_start, y_end;
        tie(x0, y_start, y_end) = vl;
        int idx_y_start = y_index[y_start];
        int idx_y_end = y_index[y_end];
        events.emplace_back(x0, 1, idx_y_start, idx_y_end); // Query event
    }

    // Sort events
    // Event types: 0 = 'add', 1 = 'query', 2 = 'remove'
    // We sort by x, then by event type ('add' before 'query' before 'remove')
    sort(events.begin(), events.end(), [](const Event &a, const Event &b) {
        if (a.x != b.x) return a.x < b.x;
        return a.type < b.type;
    });

    // Fenwick Tree (Binary Indexed Tree) implementation
    class FenwickTree {
    public:
        FenwickTree(int size) : N(size + 2) {
            tree.resize(N, 0);
        }
        void update(int idx, int value) {
            while (idx < N) {
                tree[idx] += value;
                idx += idx & -idx;
            }
        }
        int query(int idx) {
            int result = 0;
            while (idx > 0) {
                result += tree[idx];
                idx -= idx & -idx;
            }
            return result;
        }
        int range_query(int l, int r) {
            return query(r) - query(l - 1);
        }
    private:
        int N;
        vector<int> tree;
    };

    FenwickTree ft(M);

    long long result = 0;

    for (auto &event : events) {
        if (event.type == 0) {
            // Add event
            ft.update(event.y1, 1);
        } else if (event.type == 2) {
            // Remove event
            ft.update(event.y1, -1);
        } else {
            // Query event
            int y_start = event.y1;
            int y_end = event.y2;
            if (y_start > y_end) swap(y_start, y_end);
            int count = ft.range_query(y_start, y_end);
            result += count;
        }
    }

    printf("%lld\n", result);

    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