SHARE
TWEET

Untitled

a guest Oct 21st, 2019 54 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top