Guest User

electionposter

a guest
Nov 20th, 2020
166
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. using namespace std;
  6.  
  7. #define OJ \
  8. freopen("input.txt", "r", stdin); \
  9. freopen("output.txt", "w", stdout);
  10. #define FIO \
  11. ios_base::sync_with_stdio(false); \
  12. cin.tie(NULL); \
  13. cout.tie(NULL);
  14.  
  15. vector<int> lazy;
  16. int n;
  17.  
  18. void shift(int id)
  19. {
  20. if (lazy[id])
  21. {
  22. lazy[2 * id] = lazy[2 * id + 1] = lazy[id];
  23. }
  24.  
  25. lazy[id] = 0;
  26. }
  27.  
  28. void update(int x, int y, int color, int id = 1, int l = 0, int r = n)
  29. {
  30. if (x >= r || y <= l)
  31. {
  32. return;
  33. }
  34.  
  35. if (x <= l && r <= y)
  36. {
  37. lazy[id] = color;
  38. return;
  39. }
  40.  
  41. int mid = (l + r) / 2;
  42. shift(id);
  43. update(x, y, color, 2 * id, l, mid);
  44. update(x, y, color, 2 * id + 1, mid, r);
  45. }
  46.  
  47. set<int> ans;
  48. void cnt(int id = 1, int l = 0, int r = n)
  49. {
  50. if (lazy[id])
  51. {
  52. ans.insert(lazy[id]);
  53. return;
  54. }
  55.  
  56. if (r == l+1)
  57. {
  58. return;
  59. }
  60.  
  61. int mid = (l + r) / 2;
  62. cnt(2 * id, l, mid);
  63. cnt(2 * id + 1, mid, r);
  64. }
  65.  
  66. int main()
  67. {
  68. OJ;
  69. FIO;
  70. int t;
  71. cin >> t;
  72. while (t--)
  73. {
  74. ans.clear();
  75. int x;
  76. cin >> x;
  77. set<int> pts;
  78. vector<pair<int, int>> ranges(x);
  79. for (int i = 0; i < x; i++)
  80. {
  81. int l, r;
  82. cin >> l >> r;
  83. pts.insert(l);
  84. pts.insert(r);
  85. ranges[i] = make_pair(l, r);
  86. }
  87.  
  88. // range compression
  89. int k = 0;
  90. map<int, int> m;
  91. for (auto p : pts)
  92. {
  93. m[p] = k++;
  94. }
  95.  
  96. n = k;
  97. for (int i = 0; i < x; i++)
  98. {
  99. ranges[i].first = m[ranges[i].first];
  100. ranges[i].second = m[ranges[i].second];
  101. }
  102.  
  103. lazy.assign(4 * (k + 1), 0);
  104.  
  105. for (int i = 0; i < x; i++)
  106. {
  107. update(ranges[i].first, ranges[i].second + 1, i + 1);
  108. }
  109.  
  110. cnt();
  111. cout << ans.size() << "\n";
  112. }
  113. return 0;
  114. }
RAW Paste Data