[Codeforces] E. LIS of Sequence

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. LIS of Sequence
Source            : Codeforces
Category          : Dynamic Programing
Algorithm         : LIS
Verdict           : Accepted

#include <bits/stdc++.h>  
  
using namespace std;  
  
//#define int                 long long int  
#define pii                 pair <int, int>  
  
static const int maxn = 2e5 + 5;  
static const int logn = 20;  
  
int arr[maxn], lis_size[maxn], ans[maxn];  
set <pii> myset[maxn];  
  
void lis(int n)  
{  
      vector <int> vec;  
      for (int i = 1; i <= n; i++)  
      {  
            int x = arr[i];  
            auto it = lower_bound(vec.begin(), vec.end(), x);  
            lis_size[i] = int(it - vec.begin()) + 1;  
            if (it == vec.end()) vec.push_back(x);  
            else *it = x;  
      }  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int n;  
      cin >> n;  
      for (int i = 1; i <= n; i++) cin >> arr[i];  
  
      lis(n);  
  
      int max_lis = 0;  
      int ind = 0;  
      for (int i = 1; i <= n; i++)  
      {  
            if (lis_size[i] >= max_lis) max_lis = lis_size[i], ind = i;  
      }  
  
      fill(begin(ans), end(ans), 1);  
  
      for (int i = ind; i >= 1; i--)  
      {  
            int sze = lis_size[i];  
            if (sze == max_lis)  
            {  
                  myset[sze].insert(pii(arr[i], i));  
            }  
            else  
            {  
                  auto it = myset[sze+1].lower_bound(pii(arr[i] + 1, -1));  
                  if (it != myset[sze+1].end()) myset[sze].insert(pii(arr[i], i));  
            }  
      }  
      for (int i = 1; i <= n; i++)  
      {  
            int sze = lis_size[i];  
            auto it = myset[sze].find(pii(arr[i], i));  
            if (it != myset[sze].end())  
            {  
                  if (myset[sze].size() == 1) ans[i] = 3;  
                  else ans[i] = 2;  
            }  
      }  
      for (int i = 1; i <= n; i++) cout << ans[i];  
}