SHARE
TWEET

Untitled

a guest Nov 6th, 2019 18 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int CeilIndex(std::vector<int>& v, int l, int r, int key)
  5. {
  6.     while (r - l > 1) {
  7.         int m = l + (r - l) / 2;
  8.         if (v[m] >= key)
  9.             r = m;
  10.         else
  11.             l = m;
  12.     }
  13.  
  14.     return r;
  15. }
  16.  
  17. int LongestIncreasingSubsequenceLength(std::vector<int>& v)
  18. {
  19.     if (v.size() == 0)
  20.         return 0;
  21.  
  22.     std::vector<int> tail(v.size(), 0);
  23.     int length = 1; // always points empty slot in tail
  24.  
  25.     tail[0] = v[0];
  26.     for (size_t i = 1; i < v.size(); i++) {
  27.  
  28.         // new smallest value
  29.         if (v[i] < tail[0])
  30.             tail[0] = v[i];
  31.  
  32.         // v[i] extends largest subsequence
  33.         else if (v[i] > tail[length - 1])
  34.             tail[length++] = v[i];
  35.  
  36.         // v[i] will become end candidate of an existing
  37.         // subsequence or Throw away larger elements in all
  38.         // LIS, to make room for upcoming grater elements
  39.         // than v[i] (and also, v[i] would have already
  40.         // appeared in one of LIS, identify the location
  41.         // and replace it)
  42.         else
  43.             tail[CeilIndex(tail, -1, length - 1, v[i])] = v[i];
  44.     }
  45.  
  46.     return length;
  47. }
  48. int main()
  49. {
  50.     int n,a,b,i;
  51.     cin>>n;
  52.     vector<pair<int,int> >vec;
  53.     for(i=0;i<n;i++)
  54.     {
  55.         cin>>a>>b;
  56.         vec.push_back({a,b});
  57.        
  58.     }
  59.     sort(vec.begin(),vec.end());
  60.     vector<int> arr;
  61.     for(i=0;i<n;i++)
  62.     arr.push_back(vec[i].second);
  63.     cout<<LongestIncreasingSubsequenceLength(arr)<<endl;
  64.     return 0;
  65. }
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