fork(1) download
  1. /*
  2.  * Author: Tara Prasad
  3.  * Problem: POSTERS
  4.  */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. #define F first
  9. #define S second
  10. #define mp make_pair
  11. #define mt make_tuple
  12. #define pb push_back
  13. #define ALL(x) x.begin(), x.end()
  14. #define REV_ALL(x) x.rbegin(), x.rend()
  15. #define SZ(x) (int)x.size()
  16. #define CONTAINS(cont, val) (cont.find(val) != cont.end())
  17. #define endl '\n'
  18. #define what_is(x) cout << #x << " = " << x << endl
  19. #define IO_SPEED_UP ios::sync_with_stdio(false);cin.tie(NULL)
  20. #define FOR(i, st, ed, inc) for(ll i = st; i < ed; i += inc)
  21. #define leftmost_set(x) __builtin_clzll(x)
  22.  
  23. typedef long long ll;typedef pair<ll, ll> ii;
  24. typedef vector<ll> vi;typedef vector<bool> vb;
  25. typedef vector<ii> vii;typedef vector<vi> vvi;
  26.  
  27. const ll PINF = 1E9;
  28. const ll NINF = -1E9;
  29. const ll M = 1E9 + 7;
  30. const double EPS = 1E-9;
  31. const int N = 40005;
  32.  
  33. int n;
  34. vi lazy;
  35.  
  36. void shift(int id) {
  37. if(lazy[id])
  38. lazy[2 * id] = lazy[2 * id + 1] = lazy[id];
  39. lazy[id] = 0;
  40. }
  41.  
  42. void paint(int x, int y, int color, int id = 1, int l = 0,int r = n){
  43. if(x >= r or l >= y) return ;
  44. if(x <= l && r <= y){
  45. lazy[id] = color;
  46. return ;
  47. }
  48. int mid = (l+r)/2;
  49. shift(id);
  50. paint(x, y, color, 2 * id, l, mid);
  51. paint(x, y, color, 2*id+1, mid, r);
  52. }
  53.  
  54. set<int> ans;
  55. void cnt(int id = 1,int l = 0, int r = n){
  56. if(lazy[id]){
  57. ans.insert(lazy[id]);
  58. return ; // there is no need to see the children, because all the interval is from the same color
  59. }
  60. if(r == l + 1) return ;
  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. IO_SPEED_UP;
  68.  
  69. int t; cin >> t;
  70. while(t--) {
  71. ans.clear();
  72. int x; cin >> x;
  73. set<int> pts;
  74. vii ranges(x);
  75. for(int i = 0; i < x; i++) {
  76. int l, r; cin >> l >> r;
  77. pts.insert(l);
  78. pts.insert(r);
  79. ranges[i] = mp(l, r);
  80. }
  81.  
  82. // range compression
  83. int k = 0;
  84. map<int, int> m;
  85. for(auto p: pts) {
  86. m[p] = k++;
  87. }
  88.  
  89. n = k; // setting the total no. of points
  90. for(int i = 0; i < x; i++) {
  91. ranges[i].F = m[ranges[i].F];
  92. ranges[i].S = m[ranges[i].S];
  93. }
  94.  
  95. lazy.assign(4 * (k + 1), 0);
  96.  
  97. for(int i = 0; i < x; i++) {
  98. paint(ranges[i].F, ranges[i].S + 1, i + 1);
  99. }
  100.  
  101. cnt();
  102. cout << ans.size() << "\n";
  103. }
  104. return 0;
  105. }
  106.  
Success #stdin #stdout 0s 16072KB
stdin
1
5
1 4
2 6
8 10
3 4
7 10
stdout
4