fork download
copy 
  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
comments (?)
stdin
copy 
8
1 3
3 2
1 1
4 5
6 3
9 9
8 7
7 6
stdout
copy 
3
https://ideone.com/kyIJMf
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!