Advertisement
Guest User

Untitled

a guest
Aug 3rd, 2015
166
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.58 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. #include <vector>
  4. #include <hash_map>
  5. #include <algorithm>
  6. #include <utility>
  7. #include <functional>
  8. using namespace std;
  9.  
  10. template <typename type> class LIS{
  11. private:
  12. std::vector<type> vector;
  13. int DP[50001];
  14. public:
  15. void insert(type value)
  16. {
  17. if (this->vector.empty() || this->vector.back() < value)
  18. {
  19. if (!this->vector.empty())
  20. this->DP[value] = this->vector.back();
  21. this->vector.push_back(value);
  22. }
  23. else
  24. {
  25. auto arg = std::lower_bound(this->vector.begin(), this->vector.end(), value);
  26. *arg = value;
  27. if (arg != this->vector.begin())
  28. this->DP[value] = *(--arg);
  29. }
  30. }
  31. std::vector<type> result()
  32. {
  33. int res = this->vector.back();
  34. this->vector.clear();
  35. while (res != 0){
  36. vector.push_back(res);
  37. res = DP[res];
  38. }
  39. std::sort(vector.begin(), vector.end());
  40. return vector;
  41. }
  42. unsigned long size()
  43. {
  44. return this->vector.size();
  45. }
  46. };
  47. int main()
  48. {
  49. long size;
  50. std::cin >> size;
  51. std::vector<std::pair<long, long> > vec;
  52. for (long i = 0; i < size; i++)
  53. {
  54. int p, q;
  55. std::cin >> p >> q;
  56. vec.push_back({ p, q });
  57. }
  58. sort(vec.begin(), vec.end());
  59. LIS<long> a;
  60. std::for_each(vec.begin(), vec.end(), [&a](std::pair<long, long> arg){a.insert(arg.second); });
  61. std::cout << vec.size() - a.size() << std::endl;
  62. std::vector<long > result = a.result();
  63. std::for_each(result.begin(), result.end(), [&vec](long args){
  64. for (std::pair<long, long> & arg : vec)
  65. if (arg.second == args)
  66. arg.first = 0;
  67. });
  68. std::for_each(vec.begin(), vec.end(), [](std::pair<long, long> arg){ if (arg.first) std::cout << arg.first << std::endl; });
  69.  
  70. return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement