daily pastebin goal
61%
SHARE
TWEET

LIS O(nlogn) longitud y secuencia

a guest Feb 16th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <iostream>
  6. #include <map>
  7. #include <queue>
  8. #include <set>
  9. #include <stack>
  10. #include <vector>
  11.  
  12. #define ll long long
  13. #define scani(x) scanf("%i", &x)
  14. #define scanll(x) scanf("%I64d", &x)
  15. #define scanfl(x) scanf("%f", &x)
  16. #define scanch(x) scanf("%c", &x)
  17. #define scans(x) scanf("%s", x);
  18. #define printi(x) printf("%i", x);
  19. #define printll(x) printf("%I64d", x);
  20. #define printfl(x) printf("%f", x);
  21. #define printch(x) printf("%c", x);
  22. #define prints(x) printf("%s", x);
  23. #define all(x) x.begin(), x.end()
  24. #define rall(x) x.rbegin(), x.rend()
  25. #define INFI (1 << 29)
  26. #define INFL (1LL << 62)
  27. #define sz(x) int(x.size())
  28. #define forn(i, n) for (ll i = 0; i < n; i++)
  29. #define for1(i, n) for (ll i = 1; i <= n; i++)
  30. #define ford(i, n) for (ll i = (n - 1); i >= 0; i--)
  31. #define fori(i, n) for (ll i = n; i >= 1; i--)
  32. #define fore(i, l, r) for (ll i = l; i <= r; i++)
  33.  
  34. using namespace std;
  35.  
  36. ll n, v[1000000], b[1000000], LIS, ub;
  37. vector<ll> a(1000000);
  38.  
  39. ll ceilBinario(const ll &val)
  40. {
  41.     ll pos = INFL, ini = 0, fin = LIS, m;
  42.  
  43.     while ((ini + 1) < fin)
  44.     {
  45.         m = ((ini + fin) / 2);
  46.  
  47.         if (v[a[m]] < val)
  48.             ini = m;
  49.         else
  50.             fin = m, pos = min(pos, m);
  51.     }
  52.  
  53.     if (v[a[ini]] >= val)
  54.         pos = min(pos, ini);
  55.     if (v[a[fin]] >= val)
  56.         pos = min(pos, fin);
  57.  
  58.     return pos;
  59. }
  60.  
  61. void showSubsequence()
  62. {
  63.     ll i = (n - 1);
  64.  
  65.     vector < ll > seq;
  66.  
  67.     while(b[i] != (-1))
  68.     {
  69.         seq.push_back(v[i]);
  70.  
  71.         i = b[i];
  72.     }
  73.  
  74.     seq.push_back(v[i]);
  75.  
  76.     ford(i, sz(seq))
  77.         printf("%I64d ", seq[i]);
  78.     prints("\n");
  79. }
  80.  
  81. ll longestIncreasingSubsequence()
  82. {
  83.     memset(b, (-1), sizeof(b));
  84.  
  85.     LIS = 0, a[0] = 0;
  86.  
  87.     for1(i, (n - 1))
  88.     {
  89.         if (v[i] < v[a[0]])
  90.             a[0] = i;
  91.         else if (v[i] > v[a[LIS]])
  92.             a[1 + LIS++] = i, b[i] = a[LIS - 1];
  93.         else
  94.         {
  95.             ub = ceilBinario(v[i]);
  96.  
  97.             a[ub] = i, b[i] = a[ub - 1];
  98.         }
  99.     }
  100.  
  101.     return (LIS + 1);
  102. }
  103.  
  104. int main()
  105. {
  106.     scanll(n);
  107.  
  108.     forn(i, n) scanll(v[i]);
  109.  
  110.     printll(longestIncreasingSubsequence()); prints("\n");
  111.  
  112.     showSubsequence();
  113.  
  114.     return 0;
  115. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top