NgJaBach

LIS

Jan 11th, 2021 (edited)
179
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.48 KB | None
  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.  
RAW Paste Data Copied