API tools faq
paste
NgJaBach

LIS

NgJaBach
Jan 11th, 2021 (edited)
244
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.48 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long int ll;
  5. //#define isvowel(a) (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define gcd __gcd
  11. #define getl(s) getline(cin, s);
  12. #define setpre(x) fixed << setprecision(x)
  13. #define mset(a) memset(a, 0, sizeof(a))
  14. #define endl '\n'
  15. const int N=100050,M=1000000007;
  16. const ll INF=1e18+7;
  17. void fastscan(int &number){
  18. bool negative=false;
  19. register int c;
  20. number=0;
  21. c=getchar();
  22. if(c=='-'){
  23. negative=true;
  24. c=getchar();
  25. }
  26. for(;(c>47&&c<58);c=getchar()) number=number*10+c-48;
  27. if(negative) number*=-1;
  28. }
  29. int bin(vector<int>a,int L,int R,int key){
  30. int ans,mid;
  31. while(L<=R){
  32. mid=(L+R)/2;
  33. if(a[mid]>=key){
  34. ans=mid;
  35. R=mid-1;
  36. }
  37. else L=mid+1;
  38. }
  39. return ans;
  40. }
  41. void LIS(vector<int>a){
  42. int i,n=a.size(),len=1,pos;
  43. vector<int>gay(n,0);
  44. gay[0]=a[0];
  45. for(i=1;i<n;++i){
  46. if(a[i]<gay[0]) gay[0]=a[i];
  47. else if(a[i]>gay[len-1]) gay[len++]=a[i];
  48. else gay[bin(gay,0,len-1,a[i])]=a[i];
  49. }
  50. cout<<len<<endl;
  51. }
  52. //------------------------------
  53. int binpos(vector<int>a,vector<int>gay,int L,int R,int key){
  54. int ans,mid;
  55. while(L<=R){
  56. mid=(L+R)/2;
  57. if(a[gay[mid]]>=key){
  58. ans=mid;
  59. R=mid-1;
  60. }
  61. else L=mid+1;
  62. }
  63. return ans;
  64. }
  65. void LIS_print(vector<int>a){
  66. int n=a.size(),i,len=1,pos;
  67. vector<int>gay(n,0),res;
  68. vector<int>prev(n,-1);
  69. for(i=1;i<n;++i){
  70. if(a[i]<a[gay[0]]) gay[0]=i;
  71. else if(a[i]>a[gay[len-1]]){
  72. prev[i]=gay[len-1];
  73. gay[len++]=i;
  74. }
  75. else{
  76. pos=binpos(a,gay,0,len-1,a[i]);
  77. prev[i]=gay[pos-1];
  78. gay[pos]=i;
  79. }
  80. }
  81. cout<<len<<endl;
  82. for(i=gay[len-1];i>=0;i=prev[i]) res.pb(a[i]);
  83. reverse(res.begin(),res.end());
  84. for(i=0;i<len;++i) cout<<res[i]<<" ";
  85. return;
  86. }
  87. int main(){
  88. ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
  89. // freopen("DAYCONT.inp","r",stdin);
  90. // freopen("DAYCONT.out","w",stdout);
  91. int n,i,a;
  92. vector<int>gay;
  93. cin>>n;
  94. while(n--){
  95. cin>>a;
  96. gay.pb(a);
  97. }
  98. LIS(gay);
  99. return 0;
  100. }
  101. /*
  102. ==================================+
  103. INPUT: |
  104. ------------------------------ |
  105.  
  106. ------------------------------ |
  107. ==================================+
  108. OUTPUT: |
  109. ------------------------------ |
  110.  
  111. ------------------------------ |
  112. ==================================+
  113. */
  114.  
Add Comment
Please, Sign In to add comment
Public Pastes
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!