Advertisement
Guest User

Untitled

a guest
Apr 24th, 2019
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.47 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define pb push_back
  6. #define all(a) a.begin(), a.end()
  7. #define rall(a) a.rbegin(), a.rend()
  8. #define x first
  9. #define y second
  10.  
  11. void out(vector<int> a) {
  12. for (auto it = a.begin(); it != a.end(); ++it) cout << (*it) << " ";
  13. cout << "\n";
  14. }
  15.  
  16. struct sq {
  17. int ind;
  18. int x1, y1, x2, y2;
  19. };
  20.  
  21. struct node {
  22. int l, r, id = -1;
  23. };
  24.  
  25. int n;
  26. vector<sq> a;
  27. const int N = 5e5 + 47;
  28. node tree[4*N];
  29.  
  30. inline void read() {
  31. cin >> n;
  32. a.resize(n);
  33. for (int i = 0; i<n; ++i) cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
  34. }
  35.  
  36. bool comp(sq u, sq v) {
  37. if (u.y1 < v.y1) return true;
  38. else return false;
  39. }
  40.  
  41. void build(int i, int l, int r) {
  42. if (l > r) return;
  43. tree[i].l = l, tree[i].r = r;
  44. if (l == r) {
  45. tree[i].id = -1;
  46. return;
  47. }
  48. int mid = (l + r) / 2;
  49. build(2 * i, l, mid);
  50. build(2 * i + 1, mid + 1, r);
  51. }
  52.  
  53. void push (int i) {
  54. if (tree[i].id != -1 && tree[i].l != tree[i].r) {
  55. tree[2 * i].id = tree[i].id;
  56. tree[2 * i + 1].id = tree[i].id;
  57. tree[i].id = -1;
  58. }
  59. }
  60.  
  61. void upd(int i, int l, int r, int index) {
  62. push(i);
  63. if (r < tree[i].l || l > tree[i].r) return;
  64. if (tree[i].l >= l && tree[i].r <= r) {
  65. tree[i].id = index;
  66. return;
  67. }
  68. upd(2 * i, l, r, index);
  69. upd(2 * i + 1, l, r, index);
  70. }
  71.  
  72. int get_id (int i, int index) {
  73. push(i);
  74. if (index < tree[i].l || index > tree[i].r) return -1;
  75. if (tree[i].l == index && tree[i].r == index) return tree[i].id;
  76. return max(get_id(2 * i, index), get_id(2 * i + 1, index));
  77. }
  78.  
  79. inline void solve() {
  80. int ans = 0;
  81. sort(all(a), comp);
  82. build(1, 0, n - 1);
  83.  
  84. for (int i = 0; i<n; ++i) {
  85. if (get_id(1, a[i].x1) == -1) {
  86. upd(1, a[i].x1, a[i].x2, a[i].ind);
  87. ++ans;
  88. }
  89. else {
  90. int j = get_id(1, a[i].x1);
  91. cout << j << endl;
  92. if (a[i].x1 >= a[j].x1 && a[i].x1 <= a[j].x2 &&
  93. a[i].y1 >= a[j].y1 && a[i].y1 <= a[j].y2)
  94. continue;
  95. else {
  96. upd(1, a[i].x1, a[i].x2, a[i].ind);
  97. ++ans;
  98. }
  99. }
  100. }
  101. cout << ans;
  102. }
  103.  
  104. signed main() {
  105. ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  106. cout << fixed << setprecision(20);
  107. //freopen("input.in", "r", stdin);
  108. //freopen("output.out", "w", stdout);
  109. read();
  110. solve();
  111. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement