fork download
copy 
  1. #include <iostream>
  2. #include <set>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <functional>
  7. #include <string>
  8. using namespace std;
  9.  
  10. #define INF 987654321
  11.  
  12. vector<int> v;
  13.  
  14. int bs(int x,int l,int h) {
  15. 	while (l <= h) {
  16. 		if (l == h) return l+1;
  17. 		int mid = (l + h) / 2;
  18. 		if (v[mid] < x) {
  19. 			l = mid + 1;
  20. 		}
  21. 		else
  22. 			h = mid - 1;
  23. 	}
  24. 	return l;
  25. }
  26. int main() {
  27. 	ios_base::sync_with_stdio(0);
  28. 	cin.tie(0);
  29. 	cout.tie(0);
  30. 	int n;
  31. 	cin >> n;
  32. 	for (int i = 0; i < n; i++) {
  33. 		int x;
  34. 		cin >> x;
  35. 		if (v.empty()) { //비어있으면 삽입
  36. 			v.push_back(x);
  37. 		}
  38. 		else {
  39. 			int idx = bs(x, 0, v.size());
  40. 			if (idx >= v.size()) v.push_back(x);
  41. 			else {
  42. 				if (v[idx] > x && v[idx-1]<x) v[idx] = x;
  43. 				else if (v[idx] > x && v[idx - 1] > x) v[idx - 1] = x;
  44. 				//idx가 현재 사이즈보다 작을 경우
  45. 			}
  46. 		}
  47. 	}
  48.  
  49. 	cout << v.size() << endl;
  50.  
  51. 	return 0;
  52. }
Success #stdin #stdout 0s 4312KB
comments (?)
stdin
copy 
2
2 1
stdout
copy 
1
https://ideone.com/eQDgUH
language:
C++14 (gcc 8.3)
created:
4 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!