Saleh127

UVA 481 / DP - LIS

Nov 8th, 2021 (edited)
661
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-11-09-00.36.46
  3. ***/
  4.  
  5. /// LIS with path in O(NlogN)
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9. #define ll long long
  10. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  11. #define get_lost_idiot return 0
  12. #define nl '\n'
  13.  
  14. int main()
  15. {
  16.    ios_base::sync_with_stdio(0);
  17.    cin.tie(0);cout.tie(0);
  18.  
  19.    ll n=0,m=1,i,j,k,l;
  20.  
  21.    vector<ll>a,lis,path;
  22.  
  23.    while(cin>>k)
  24.    {
  25.         n++;
  26.         a.push_back(k);
  27.    }
  28.  
  29.    ll dp[n+4];
  30.  
  31.    dp[0]=1;
  32.  
  33.    lis.push_back(a[0]);
  34.  
  35.    for(i=1;i<n;i++)
  36.    {
  37.         if(a[i]>lis[lis.size()-1])
  38.         {
  39.              lis.push_back(a[i]);
  40.              m++;
  41.              dp[i]=m;
  42.         }
  43.         else
  44.         {
  45.              l=lower_bound(lis.begin(),lis.end(),a[i])-lis.begin();
  46.              dp[i]=l+1;
  47.              lis[l]=a[i];
  48.         }
  49.    }
  50.  
  51.    for(i=n-1;i>=0;i--)
  52.    {
  53.         if(dp[i]==m)
  54.         {
  55.              path.push_back(a[i]);
  56.              m--;
  57.         }
  58.    }
  59.  
  60.    cout<<path.size()<<nl<<"-"<<nl;
  61.  
  62.    for(i=path.size()-1;i>=0;i--)
  63.    {
  64.         cout<<path[i]<<nl;
  65.    }
  66.  
  67.    get_lost_idiot;
  68. }
  69.  
RAW Paste Data Copied