• API
• FAQ
• Tools
• Archive
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.

Top