fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 100000 + 10;
  6.  
  7. struct Event {
  8.     int x, y1, y2;
  9.     bool isleft;
  10. };
  11.  
  12. struct Node {
  13.     int cnt, len, tot;
  14. };
  15.  
  16. Event e[N * 2];
  17. Node sgt[N * 8];
  18.  
  19. bool cmp(const Event& a, const Event& b) { return a.x < b.x; }
  20.  
  21. void build(int index, int begin, int end) {
  22.     sgt[index].tot = end - begin + 1;
  23.     if (begin >= end)
  24.         return;
  25.     int mid = (begin + end) / 2;
  26.     build(index * 2, begin, mid);
  27.     build(index * 2 + 1, mid + 1, end);
  28. }
  29.  
  30. void push_up(int index) {
  31.     if (sgt[index].cnt > 0)
  32.         sgt[index].len = sgt[index].tot;
  33.     else
  34.         sgt[index].len = sgt[index * 2].len + sgt[index * 2 + 1].len;
  35. }
  36.  
  37. void update(int index, int begin, int end, int left, int right, int val) {
  38.     if (left <= begin && right >= end) {
  39.         sgt[index].cnt += val;
  40.         push_up(index);
  41.         return;
  42.     }
  43.     int mid = (begin + end) / 2;
  44.     if (right <= mid)
  45.         update(index * 2, begin, mid, left, right, val);
  46.     else if (left > mid)
  47.         update(index * 2 + 1, mid + 1, end, left, right, val);
  48.     else {
  49.         update(index * 2, begin, mid, left, mid, val);
  50.         update(index * 2 + 1, mid + 1, end, mid + 1, right, val);
  51.     }
  52.     push_up(index);
  53. }
  54.  
  55. int main() {
  56.     long long res = 0;
  57.     int n, m = 0, t = 0, x1, y1, x2, y2;
  58.     scanf("%d", &n);
  59.     for (int i = 0; i < n; i++) {
  60.         scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
  61.         if (y1 == y2)
  62.             continue;
  63.         e[t] = { x1, y1, y2, true };
  64.         e[t + 1] = { x2, y1, y2, false };
  65.         m = max(m, y2);
  66.         t += 2;
  67.     }
  68.     build(1, 0, m - 1);
  69.     sort(e, e + t, cmp);
  70.     update(1, 0, m - 1, e[0].y1, e[0].y2 - 1, 1);
  71.     for (int i = 1; i < t; i++) {
  72.         res += 1LL * (e[i].x - e[i - 1].x) * sgt[1].len;
  73.         if (e[i].isleft)
  74.             update(1, 0, m - 1, e[i].y1, e[i].y2 - 1, 1);
  75.         else
  76.             update(1, 0, m - 1, e[i].y1, e[i].y2 - 1, -1);
  77.     }
  78.     printf("%lld\n", res);
  79.     return 0;
  80. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Dc1YHo
language:
C++ (gcc 8.3)
created:
7 days 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!