Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2019
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.20 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define loop(i,n) for(int i=0; i<n; i++)
  6. #define all(a) a.begin(),a.end()
  7. #define fr first
  8. #define sc second
  9.  
  10. int INF=1e9;
  11.  
  12. struct node{
  13. int he,l,r,ch;
  14. node ()
  15. {
  16. he = ch = INF;
  17. }
  18. };
  19.  
  20. const int n = 5e5 * 4;
  21. node tree[n];
  22. pair <pair <int,int> , pair <int,int> > ar[50000];
  23.  
  24. void push(int v)
  25. {
  26. if (tree[v].ch != INF && tree[v].l!=tree[v].r)
  27. {
  28. tree[v*2].he = tree[v].ch;
  29. tree[v*2+1].he = tree[v].ch;
  30. tree[v*2].ch = tree[v].ch;
  31. tree[v*2+1].ch = tree[v].ch;
  32. tree[v].ch = INF;
  33. }
  34. }
  35.  
  36. void build_tree(int v, int l, int r)
  37. {
  38. if (l > r) return;
  39. tree[v].l = l; tree[v].r = r;
  40. if (l == r)
  41. {
  42. tree[v].he = -1;
  43. return;
  44. }
  45. int mid = (l + r)/2;
  46. build_tree(v*2, l, mid);
  47. build_tree(v*2+1, mid+1, r);
  48. tree[v].he = max (tree[v*2].he, tree[v*2+1].he);
  49. }
  50.  
  51. int find_max(int v, int l)
  52. {
  53. push(v);
  54. if (tree[v].l > l || tree[v].r < l) return -1e5;
  55. if (tree[v].l == tree[v].r && tree[v].l == l) return tree[v].he;
  56. return max(find_max(v*2, l),find_max(v*2+1, l));
  57. }
  58.  
  59. void upd(int v, int l, int r, int nw)
  60. {
  61. //cout << tree[v].ch;
  62. push(v);
  63. if (tree[v].l > r || tree[v].r < l) return;
  64. if (tree[v].l >= l && tree[v].r <= r)
  65. {
  66. tree[v].ch = nw;
  67. tree[v].he = nw;
  68. return;
  69. }
  70. //int mid = (l+r)/2;
  71. upd(v*2, l , r , nw);
  72. upd(v*2+1, l , r , nw);
  73. tree[v].he = max(tree[v*2].he, tree[v*2+1].he);
  74. }
  75.  
  76. signed main()
  77. {
  78. int n;
  79. cin >> n;
  80. loop(i,50001)
  81. {
  82. ar[i].fr.fr = INF;
  83. ar[i].fr.sc = INF;
  84. ar[i].sc.fr = INF;
  85. ar[i].sc.sc = INF;
  86. }
  87. loop(i,n)
  88. {
  89. int x1,y1,x2,y2;
  90. cin >> x1 >> y1 >> x2 >> y2;
  91. ar[i].fr.fr = x1;
  92. ar[i].fr.sc = x2;
  93. ar[i].sc.fr = y1;
  94. ar[i].sc.sc = y2;
  95. }
  96.  
  97. int ans=0;
  98. sort(ar, ar + 50001);
  99. build_tree(1, 0, 5e5);
  100. loop(i,n)
  101. {
  102. if (find_max(1,ar[i].sc.fr) < ar[i].fr.fr)
  103. {
  104. ans++;
  105. upd(1, ar[i].sc.fr, ar[i].sc.sc, ar[i].fr.sc);
  106. }
  107. }
  108. cout << ans;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement