• API
• FAQ
• Tools
• Archive
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 = v;
26.     for (size_t i = 1; i < v.size(); i++) {
27.
28.         // new smallest value
29.         if (v[i] < tail)
30.             tail = 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.

Top