fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. struct data {
  7. 	int x, l, r, type;
  8. };
  9.  
  10. struct seg {
  11. 	int cnt;
  12. 	ll len;
  13. };
  14.  
  15. const int N = 2e5 + 5;
  16.  
  17. int n, m, k;
  18. ll ans;
  19. ll values[N];
  20. data a[N];
  21. seg t[4*N];
  22.  
  23. bool cmp(data u, data v) {
  24. 	return (u.x < v.x || (u.x == v.x && u.type < v.type));
  25. }
  26.  
  27. void update(int id, int l, int r, int u, int v, int type) {
  28.  
  29. 	if (r < u || v < l) return ;
  30. 	if (u <= l && r <= v) {
  31. 		t[id].cnt += type;
  32. 		if (type == 1) t[id].len = values[r] - values[l - 1];
  33. 		else if (t[id].cnt == 0) if (l < r) t[id].len = t[id * 2].len + t[id * 2 + 1].len;
  34. 		else t[id].len = 0;
  35. 		return ;
  36. 	}
  37. 	int mid = (l + r) / 2;
  38. 	update(id * 2, l, mid, u, v, type);
  39. 	update(id * 2 + 1, mid + 1, r, u, v, type);
  40. 	if (t[id].cnt == 0 && l < r) t[id].len = t[id * 2].len + t[id * 2 + 1].len;
  41. }
  42.  
  43. int main() {
  44. ios_base::sync_with_stdio(0);
  45. cin.tie(0);
  46.  
  47. 	cin >> n;
  48. 	vector<int> cost;
  49. 	for (int i = 1; i <= n; i++) {
  50. 		int x1, y1, x2, y2;
  51. 		cin >> x1 >> y1 >> x2 >> y2;
  52. 		a[++m] = {x1, y1, y2, 1};
  53. 		a[++m] = {x2, y1, y2, -1};
  54. 		cost.push_back(y1);
  55. 		cost.push_back(y2);
  56. 	}
  57. 	sort(cost.begin(), cost.end());
  58. 	cost.resize(unique(cost.begin(), cost.end()) - cost.begin());
  59. 	sort(a+1,a+m+1,cmp);
  60. 	for (int i = 1; i <= m; i++) {
  61. 		int l = a[i].l;
  62. 		int m = lower_bound(cost.begin(), cost.end(), a[i].l) - cost.begin() + 1;
  63. 		a[i].l = m;
  64. 		values[m] = l;
  65. 		int r = a[i].r;
  66. 		int m_ = lower_bound(cost.begin(), cost.end(), a[i].r) - cost.begin() + 1;
  67. 		a[i].r = m_;
  68. 		values[m_] = r;
  69. 		k = max(k, a[i].r);
  70. 	}
  71. 	for (int i = 1; i <= m; i++) {
  72. 		ans += (ll)t[1].len * (ll)(a[i].x - a[i-1].x);
  73. //		cout << ans << " - > ";
  74. //		cout << t[1].len << " - > ";
  75. 		update(1, 1, k, a[i].l + 1, a[i].r, a[i].type);
  76. 	}
  77. 	cout << ans;
  78. 	return 0;
  79. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TRkygt
language:
C++ (gcc 8.3)
created:
3 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!