Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 100000;
- struct Event {
- int x;
- int y1, y2; // vertical line
- int type; // 0, 1, 2
- Event() { }
- Event(int x, int y1, int y2, int type): x(x), y1(y1), y2(y2), type(type) { }
- };
- int fw[N + 1];
- vector<Event> events;
- vector<int> coord;
- void update(int index, int value) {
- for (; index <= N; 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(Event a, Event b) {
- if (a.x == b.x) return a.type < b.type;
- return a.x < b.x;
- }
- int main() {
- ios_base::sync_with_stdio(0), cin.tie(0);
- int n;
- cin >> n;
- for (int i = 1; i <= n; i++) {
- int x1, y1, x2, y2;
- cin >> x1 >> y1 >> x2 >> y2;
- x1 += 1e6, y1 += 1e6, x2 += 1e6, y2 += 1e6;
- if (x1 == x2) {
- // vertical line
- events.push_back(Event(x1, y1, y2, 1));
- } else {
- // horizontal line
- events.push_back(Event(x1, y1, y2, 0));
- events.push_back(Event(x2, y1, y2, 2));
- }
- coord.push_back(y1);
- coord.push_back(y2);
- }
- sort(coord.begin(), coord.end());
- coord.resize(unique(coord.begin(), coord.end()) - coord.begin());
- sort(events.begin(), events.end(), comp);
- long long ans = 0;
- for (Event e: events) {
- if (e.type == 1) {
- ans += query(e.y2) - query(e.y1 - 1);
- } else if (e.type == 0) {
- update(e.y1, 1);
- } else if (e.type == 2) {
- update(e.y2, -1);
- }
- }
- cout << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
