fork(1) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. typedef long long ll;
  4. ll n,id,l,r,m;
  5. pair<ll,ll>p[100001],lis[100001];
  6. int main()
  7. {
  8. 	cin>>n;
  9.  
  10. 	for(ll i = 1;i<=n;++i)
  11. 		cin>>p[i].first>>p[i].second;
  12.  
  13. 	lis[id++] = p[1];
  14.  
  15. 	for(ll i = 2;i<=n;++i){
  16. 		if(p[i].first < lis[0].first && p[i].second < lis[0].second)
  17. 			lis[0] = p[i];
  18. 		else if(p[i].first > lis[id-1].first && p[i].second > lis[id-1].second)
  19. 			lis[id++] = p[i];
  20. 		else{
  21.  
  22. 			l = 0;
  23. 			r = id-1;
  24.  
  25. 			while(r > l+1){
  26. 				m = (l+r)/2;
  27.  
  28. 				if(p[i].first < lis[m].first && p[i].second < lis[m].second)
  29. 					r = m;
  30. 				else
  31. 					l = m;
  32. 			}
  33.  
  34. 			lis[r] = p[i];
  35. 		}
  36. 	}
  37.  
  38. 	cout<<id<<endl;
  39. }
Success #stdin #stdout 0s 6584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/rmaQSE
language:
C++ (gcc 8.3)
created:
8 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!