Guest User

Untitled

a guest
Sep 1st, 2013
396
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a[100009];
  4. int n;
  5. int dp[100009],pos[100009],ans,it[100009][3],mx2,cbp,a2[100009];
  6. int bp[100009];
  7.  
  8. int get(int ps)
  9. {
  10.     int mx=0;
  11.     int fenwickIndex=0;
  12.     while(ps!=0)
  13.     {
  14.         if(it[ps][1]>mx)
  15.         {
  16.             mx=it[ps][1];
  17.             fenwickIndex = ps;
  18.         }
  19.         ps-=(ps&-ps);
  20.     }
  21.     return fenwickIndex;
  22. }
  23. void update(int ps,int val, int extraField)
  24. {
  25.     while(ps<=n)
  26.     {
  27.         if(it[ps][1]<val)
  28.         {
  29.             it[ps][1]=val;
  30.             it[ps][2]=extraField;
  31.         }
  32.         ps+=(ps&-ps);
  33.     }
  34. }
  35. void outputseq(int pm)
  36. {
  37.     cout<<pm<<endl;
  38.     while(pm!=0)
  39.     {
  40.         cout<<a2[pm]<<" ";
  41.         pm=bp[pm];
  42.     }
  43.     cout<<endl;
  44. }
  45. int main()
  46. {
  47.     ios::sync_with_stdio(false);
  48.     cin>>n;
  49.     for(int i=1;i<=n;i++)cin>>a[i],a2[i]=a[i],pos[a[i]]=i;
  50.     for(int i=1;i<=n;i++)
  51.     {
  52.         int fenwickIndex = get(a[i]-1);
  53.         ans=it[fenwickIndex][1];
  54.         bp[i] = it[fenwickIndex][2];
  55.         update(a[i],ans+1, i);
  56.         mx2=max(ans+1,mx2);
  57.         dp[i]=ans+1;
  58.     }
  59.     cout<<mx2<<endl;
  60.    
  61.     for(int i=1;i<=n;i++)
  62.     {
  63.         if(dp[i]==mx2)
  64.         {
  65.             outputseq(i);
  66.             return 0;
  67.         }
  68.     }
  69. }
RAW Paste Data