Advertisement
Saleh127

Light OJ 1421 / LIS

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