fork download
  1. #include<iostream>
  2. #include<map>
  3. using namespace std;
  4.  
  5. map<int, pair<int,int> > m1;
  6. map<int, pair<int,int> > :: iterator it;
  7.  
  8. int p;
  9.  
  10. int find_pos(int ar[], int low, int high, int curr)
  11. {
  12. p=-1;
  13. int mid;
  14. while(low<high)
  15. {
  16. mid= (low+high)/2;
  17. if(m1[mid].first <= m1[curr].first && m1[mid].second<=m1[curr].second)
  18. {
  19. low=mid+1;
  20. p=low;
  21. }
  22. else if(m1[mid].first >= m1[curr].first && m1[mid].second>=m1[curr].second)
  23. {
  24. high=mid-1;
  25. p=high;
  26. }
  27.  
  28. }
  29.  
  30. if(p==-1)
  31. return mid;
  32. else return p;
  33. }
  34.  
  35. int main()
  36. {
  37. int n,minx=1000000000,miny=1000000000,pos;
  38. cin>>n;
  39. int c[n+1],cnt=0;
  40. int x,y,i;
  41. for(i=0;i<n;i++)
  42. {
  43. cin>>x>>y;
  44. if(x<=minx)
  45. {
  46. minx=x;
  47. if(y<miny) {
  48. miny=y;
  49. pos=i;
  50. }
  51. }
  52. m1.insert(pair<int, pair<int,int> >(i, make_pair(x, y)));
  53. }
  54. /*
  55. cout<<"the entry with least value is "<<minx<<" "<<miny<<"at position "<<pos<<endl;
  56.  
  57. cout<<"The map has entries\n";
  58.  
  59. for(i=0;i<n;i++)
  60. {
  61. cout<<m1[i].first<<" "<<m1[i].second<<endl;
  62. }
  63. */
  64.  
  65. i=0;
  66. int sz=0;
  67. c[sz]=pos;
  68. while(i<n)
  69. {
  70. if(i==pos) i++;
  71.  
  72. if(m1[i].first>=m1[c[sz]].first && m1[i].second>=m1[c[sz]].second)
  73. {
  74. sz=sz+1;
  75. cnt++;
  76. c[sz]=i;
  77. }
  78. else if(m1[i].first<=m1[c[sz]].first && m1[i].second<=m1[c[sz]].second)
  79. {
  80. int p = find_pos(c,0,sz,i);
  81. if(p!=-1) // indicates that the element can be inserted in the array
  82. {
  83. if(m1[c[p]].first<m1[i].first && m1[c[p]].second< m1[i].second)
  84. p=p+1;
  85. c[p]=i;
  86. }
  87. }
  88. i++;
  89. }
  90.  
  91. cout<<cnt<<endl;
  92. //cout<<"length of lis is "<<cnt<<endl;
  93.  
  94. return 0;
  95. }
Success #stdin #stdout 0s 3480KB
stdin
8
1 3
3 2
1 1
4 5
6 3
9 9
8 7
7 6
stdout
3