fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAX_N = 1e6 + 10;
  5. ll total_len = 0;
  6. struct scanline {
  7.     ll x1, x2, y;
  8.     int flag;
  9.     bool operator<(const scanline& other) const {return y < other.y;}
  10. };
  11. struct seg {
  12.     int ld, rd, cover; 
  13.     ll len;
  14. };
  15. int n;
  16. ll xs[MAX_N * 2];
  17. scanline lines[MAX_N * 2];
  18. seg tnode[MAX_N * 4];
  19. #define lson(x)  ((x) << 1)
  20. #define rson(x) ((x) << 1 | 1)
  21. void build(int id, int ld, int rd) {
  22.     tnode[id].ld = ld;
  23.     tnode[id].rd = rd;
  24.     tnode[id].cover = 0;
  25.     tnode[id].len = 0;
  26.     if (ld == rd) return;
  27.     int mid = (ld + rd) / 2;
  28.     build(lson(id), ld, mid);
  29.     build(rson(id), mid + 1, rd);
  30. }
  31.  
  32. void update1(int id) {
  33.     if (tnode[id].cover > 0) tnode[id].len = xs[tnode[id].rd + 1] - xs[tnode[id].ld];
  34.     else {
  35.         if (tnode[id].ld == tnode[id].rd) tnode[id].len = 0;
  36.         else tnode[id].len = tnode[lson(id)].len + tnode[rson(id)].len;
  37.     }
  38. }
  39.  
  40. void update2(int id, ll x1, ll x2, int flag) {
  41.     if (xs[tnode[id].rd + 1] <= x1 || x2 <= xs[tnode[id].ld]) return;
  42.     if (x1 <= xs[tnode[id].ld] && xs[tnode[id].rd + 1] <= x2) {
  43.         tnode[id].cover += flag;
  44.         update1(id);
  45.         return;
  46.     }
  47.     update2(lson(id), x1, x2, flag);
  48.     update2(rson(id), x1, x2, flag);
  49.     update1(id);
  50. }
  51.  
  52. int x1[5010], yy1[5010], x2[5010], y2[5010];
  53. int main() {
  54. 	cin >> n;
  55.     for (int i = 0; i < n; ++i) {
  56.     	cin >> x1[i] >> yy1[i] >> x2[i] >> y2[i];
  57.         xs[i * 2] = x1[i];
  58.         xs[i * 2 + 1] = x2[i];
  59.         lines[i * 2] = {x1[i], x2[i], yy1[i], 1}; 
  60.         lines[i * 2 + 1] = {x1[i], x2[i], y2[i], -1};
  61.     }
  62.     int lines_cnt = n * 2;
  63.     sort(xs, xs + lines_cnt);
  64.     int xlen = unique(xs, xs + lines_cnt) - xs;
  65.     build(1, 0, xlen - 2);
  66.     sort(lines, lines + lines_cnt);
  67.     int pre = 0;
  68.     for (int i = 0; i < lines_cnt; ++i) {
  69.         update2(1, lines[i].x1, lines[i].x2, lines[i].flag);
  70.         total_len += abs(tnode[1].len - pre);
  71.  
  72.         cout << tnode[1].len - pre << endl;
  73.         pre = tnode[1].len;
  74.     }
  75.     for (int i = 0; i < n; ++i) {
  76.         xs[i * 2] = yy1[i];
  77.         xs[i * 2 + 1] = y2[i];
  78.         lines[i * 2] = {yy1[i], y2[i], x1[i], 1}; 
  79.         lines[i * 2 + 1] = {yy1[i], y2[i], x2[i], -1};
  80.     }
  81.     lines_cnt = n * 2;
  82.     sort(xs, xs + lines_cnt);
  83.     xlen = unique(xs, xs + lines_cnt) - xs;
  84.     build(1, 0, xlen - 2);
  85.     sort(lines, lines + lines_cnt);
  86.     pre = 0;
  87.     for (int i = 0; i < lines_cnt; ++i) {
  88.         update2(1, lines[i].x1, lines[i].x2, lines[i].flag);
  89.         total_len += abs(tnode[1].len - pre);
  90.  
  91.         cout << abs(tnode[1].len - pre) << endl;
  92.         pre = tnode[1].len;
  93.     }
  94.     cout << total_len;
  95.     return 0;
  96. }
Success #stdin #stdout 0.01s 7548KB
comments (?)
stdin
copy 
7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16
stdout
copy 
16
8
15
6
-10
10
-10
4
-4
0
-4
-6
0
-25
10
15
6
0
4
0
4
2
11
18
10
10
4
16
228
https://ideone.com/vhb4L2
language:
C++14 (gcc 8.3)
created:
8 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!