Guest User

Untitled

a guest
Oct 21st, 2019
55
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. using namespace std;
  5. int n;
  6. int map[1000002];
  7. int p1[1000002];
  8. int t[1000002];
  9. stack<int> st;
  10. int main() {
  11. cin>>n;
  12. for(int i=1; i<=n; i++)
  13. scanf("%d",&map[i]);
  14. t[1]=map[1];
  15. p1[1]=1;
  16. int pIndex=1;
  17. for(int i=2; i<=n; i++) {
  18. if(map[i]>t[pIndex]) {
  19. pIndex++;
  20. p1[i]=pIndex;
  21. t[pIndex]=map[i];
  22. } else {
  23. int lowIndex = lower_bound(t+1, t+pIndex, map[i])-t;
  24. p1[i]=lowIndex;
  25. t[lowIndex]=map[i];
  26. }
  27. }
  28. int len = pIndex;
  29. for(int i=n; i>=1; i--){
  30. if(p1[i]==len) {
  31. st.push(map[i]);
  32. len--;
  33. }
  34. }
  35. cout<<pIndex<<endl;
  36. while (!st.empty()) {
  37. printf("%d ",st.top());
  38. st.pop();
  39. }
  40. cout<<endl;
  41. }
RAW Paste Data