fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define ld long double
  6.  
  7. using namespace std;
  8.  
  9. struct Point
  10. {
  11.     int v;
  12.     ld x, y, y_t;
  13.  
  14.     Point(ld x = 0, ld y = 0, int v = 0, ld y_t = 0) :
  15.         v(v), x(x), y(y), y_t(y_t) {};
  16.     bool operator < (const Point &other) const
  17.     {
  18.         if (x != other.x)
  19.             return x < other.x;
  20.         return v < other.v;
  21.     }
  22. };
  23.  
  24. const int maxn = 3e5;
  25.  
  26. int n, bit[maxn + 10];
  27. ll ans = 0;
  28. vector<Point> points;
  29. vector<ld> v;
  30.  
  31. int get_id(ld x)
  32. {
  33.     return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
  34. }
  35. void update(int x, int v)
  36. {
  37.     for (; x <= maxn; x += x&-x)
  38.         bit[x] += v;
  39. }
  40. int get(int x)
  41. {
  42.     int ans = 0;
  43.     for (;x; x &= x - 1)
  44.         ans += bit[x];
  45.     return ans;
  46. }
  47.  
  48. int main()
  49. {
  50.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  51.     if (fopen("SEGMENT.INP", "r"))
  52.     {
  53.         freopen("SEGMENT.INP", "r", stdin);
  54.         freopen("SEGMENT.OUT", "w", stdout);
  55.     }
  56.  
  57.     cin >> n;
  58.     for (int i = 1; i <= n; i++)
  59.     {
  60.         ld x_a, x_b, y;
  61.         cin >> x_a >> x_b >> y;
  62.         if (x_a > x_b)
  63.             swap(x_a, x_b);
  64.         points.push_back(Point(x_a, y, 1));
  65.         points.push_back(Point(x_b, y, -1));
  66.         v.push_back(y);
  67.     }
  68.     for (int i = 1; i <= n; i++)
  69.     {
  70.         ld y_a, y_b, x;
  71.         cin >> y_a >> y_b >> x;
  72.         if (y_a > y_b)
  73.             swap(y_a, y_b);
  74.         points.push_back(Point(x, y_a, 3, y_b));
  75.         v.push_back(y_a);
  76.         v.push_back(y_b);
  77.     }
  78.     sort(points.begin(), points.end());
  79.     sort(v.begin(), v.end());
  80.     v.resize(unique(v.begin(), v.end()) - v.begin());
  81.  
  82.     for (Point p : points)
  83.     {
  84. //        cout << p.x << ' ' << p.y << ' ' << p.y_t << ' ' << p.v, el;
  85.         if (p.v == 3)
  86.             ans += get(get_id(p.y_t)) - get(get_id(p.y) - 1);
  87.         else
  88.             update(get_id(p.y), p.v);
  89. //        cout << ans, el;
  90.     }
  91.     cout << ans;
  92. }
  93.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/B7w8cK
language:
C++14 (gcc 8.3)
created:
17 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!