Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAX_UNIQUE_Y = 200005;
- struct Event {
- int x;
- int y1, y2;
- int type;
- Event() {}
- Event(int x, int y1, int y2, int type) : x(x), y1(y1), y2(y2), type(type) {}
- };
- int fw[MAX_UNIQUE_Y];
- vector<Event> events;
- vector<int> y_coords;
- void update(int index, int value, int max_coord) {
- for (; index <= max_coord; index += index & -index) {
- fw[index] += value;
- }
- }
- int query(int index) {
- int ans = 0;
- for (; index > 0; index -= index & -index) {
- ans += fw[index];
- }
- return ans;
- }
- bool comp(const Event& a, const Event& b) {
- if (a.x != b.x) {
- return a.x < b.x;
- }
- return a.type < b.type;
- }
- int get_compressed_y(int y) {
- return lower_bound(y_coords.begin(), y_coords.end(), y) - y_coords.begin() + 1;
- }
- int main() {
- ios_base::sync_with_stdio(0), cin.tie(0);
- int n;
- cin >> n;
- int offset = 1000000;
- for (int i = 0; i < n; i++) {
- int x1, y1, x2, y2;
- cin >> x1 >> y1 >> x2 >> y2;
- x1 += offset; y1 += offset;
- x2 += offset; y2 += offset;
- if (x1 == x2) {
- if (y1 > y2) swap(y1, y2);
- events.push_back(Event(x1, y1, y2, 1));
- y_coords.push_back(y1);
- y_coords.push_back(y2);
- } else {
- if (x1 > x2) swap(x1, x2);
- events.push_back(Event(x1, y1, 0, 0));
- events.push_back(Event(x2, y1, 0, 2));
- y_coords.push_back(y1);
- }
- }
- sort(y_coords.begin(), y_coords.end());
- y_coords.resize(unique(y_coords.begin(), y_coords.end()) - y_coords.begin());
- int max_compressed_y = y_coords.size();
- sort(events.begin(), events.end(), comp);
- long long ans = 0;
- for (const auto& e : events) {
- if (e.type == 0) {
- int compressed_y = get_compressed_y(e.y1);
- update(compressed_y, 1, max_compressed_y);
- } else if (e.type == 2) {
- int compressed_y = get_compressed_y(e.y1);
- update(compressed_y, -1, max_compressed_y);
- } else {
- int compressed_y1 = get_compressed_y(e.y1);
- int compressed_y2 = get_compressed_y(e.y2);
- ans += query(compressed_y2) - query(compressed_y1 - 1);
- }
- }
- cout << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
