Ganesh1648

Inversion Graphs

Jun 13th, 2020
137
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.51 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define pb push_back
  7. #define vi vector<int>
  8. #define vpii vector<pair<int, int>>
  9. #define N (int)2e5 + 5
  10. #define f first
  11. #define s second
  12. #define all(x) x.begin(), x.end()
  13. #define forn(i, n) for (int i = 0; i < n; i++)
  14. #define fore(i, l, r) for (int i = l; i < r; i++)
  15. #define sz(a) (int)((a).size())
  16. #define ll long long
  17. #define ar array
  18. #define init(arr) memset(arr, 0, sizeof(arr))
  19. #define endl "\n"
  20. #define mp make_pair
  21.  
  22. int n;
  23. int a[N];
  24. int temp[N];
  25. void solve()
  26. {
  27.     int len=0;
  28.     forn(i,n)
  29.         temp[i]=0;
  30.     temp[0]=0;
  31.     for(int i=1;i<n;i++)
  32.     {
  33.         if(a[i]>a[temp[len]])
  34.         {
  35.             len++;
  36.             temp[len]=i;
  37.         }
  38.         else
  39.         {
  40.             if(a[temp[0]]>a[i])
  41.                 temp[0]=i;
  42.             else
  43.             {
  44.                 int l=0,r=len;
  45.                 int ans=-1;
  46.                 while(l<=r)
  47.                 {
  48.                     int mid=l+(r-l)/2;
  49.                     if(a[temp[mid]]>a[i])
  50.                     {
  51.                         ans=mid;
  52.                         r=mid-1;
  53.                     }
  54.                     else
  55.                         l=mid+1;
  56.                 }
  57.                 if(ans!=-1)
  58.                     temp[ans]=i;
  59.             }
  60.         }
  61.     }
  62.     cout<<(len+1)<<endl;
  63. }
  64. int main()
  65. {
  66.     ios_base::sync_with_stdio(false);
  67.     cin.tie(NULL);
  68.     cin>>n;
  69.     for(int i=n-1;i>=0;i--)
  70.         cin>>a[i];
  71.     solve();
  72. }
Add Comment
Please, Sign In to add comment