Advertisement
Falak_Ahmed_Shakib

longest common subsenuenc by lower bound

Apr 14th, 2020
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.97 KB | None | 0 0
  1. // In the name of Allah.
  2. // We're nothing and you're everything.
  3. // Ya Ali!
  4. /*
  5. , \ / ,
  6. / \ )\__/( / \
  7. / \ (_\ /_) / \
  8. ____/_____\__\@ @/___/_____\____
  9. | |\../| |
  10. | \VV/ |
  11. | ------___------- |
  12. |__________Chuta Dragon___________|
  13. | /\ / \\ \ /\ |
  14. | / V )) V \ |
  15. |/ ` // ' \|
  16. ` V '
  17. */
  18.  
  19. #include<bits/stdc++.h>
  20. using namespace std;
  21. typedef long long ll;
  22. #define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL))
  23. #define fi first
  24. #define se second
  25. #define pb push_back
  26. ll const MOD=1000000007;
  27. ///-------------------------------------------------------------------------------------------------///
  28. /// KARMA IS LIKE 69,,, YOU GET WHAT YOU GIVE ///
  29. ///-------------------------------------------------------------------------------------------------///
  30.  
  31.  
  32.  
  33. #define eb emplace_back
  34.  
  35.  
  36.  
  37. int main()
  38. {
  39. fastread();
  40.  
  41. ll n;
  42.  
  43.  
  44. cin>>n;
  45.  
  46. ll ara[n+1]={0},bra[n+1];
  47.  
  48.  
  49. for(ll i=0;i<n;i++)
  50. {
  51. cin>>ara[i];
  52. }
  53. for(ll i=0;i<n;i++)
  54. {
  55.  
  56. cin>>bra[i];
  57. m[i+1]
  58.  
  59. }
  60.  
  61.  
  62. ll m[n+1];
  63.  
  64.  
  65.  
  66.  
  67. for(ll i=1;i<=n;i++)
  68. {
  69. cout<<"m ="<<i<<" "<<m[i]<<endl;
  70. }
  71.  
  72.  
  73.  
  74. vector<ll>v;
  75.  
  76. ll num;
  77.  
  78. for(ll i=1;i<=n;i++)
  79. {
  80. num=m[i];
  81.  
  82. vector<ll>::iterator iv=lower_bound(v.begin(),v.end(),num);
  83.  
  84. if(v.end()==iv)
  85. { cout<<num<<" = num"<<endl;
  86. v.push_back(num);
  87. }
  88. else {
  89. cout<<iv-v.begin()<<" pos "<<" num="<<num<<endl;
  90. v[iv-v.begin()]=num;
  91. }
  92.  
  93. }
  94.  
  95. for(auto x:v)cout<<x<<" ";
  96. cout<<endl;
  97.  
  98.  
  99. cout<<v.size()<<endl;
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement